Pəncərə hərəkət edərkən maksimumu necə elan etmək və saxlamaq olar?

Fərz edək ki, pəncərənin maksimumunu saxlamaq üçün tez-tez istifadə olunan məlumat quruluşu — iki tərəfli növbə (deque). Fikir odur ki, elementlərin indekslərini azalan dəyər sırasına görə saxlamaq, belə ki:

• Yeni element əlavə edilərkən, sonundan bütün kiçik elementlər silinir, çünki onlar maksimum ola bilməz.
• Pəncərə hərəkət etdikdə, pəncərədən çıxmış elementlər əvvəldən silinir.

Bu, cari pəncərədə maksimumu O(1) vaxtda almağa imkan verir və bütün massivə O(n) vaxtında işləməyə imkan verir.

Python nümunəsi:

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()  # indeksləri saxlayır
    result = []
    for i, num in enumerate(nums):
        while dq and nums[dq[-1]] < num:
            dq.pop()
        dq.append(i)
        if dq[0] == i - k:
            dq.popleft()
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

# İstifadə nümunəsi
print(max_sliding_window([1,3,-1,-3,5,3,6,7], 3))  # [3,3,5,5,6,7]