Hogyan lehet deklarálni és fenntartani a maximumot az ablak eltolásakor?

Az ablak maximális értékének fenntartásához az ablak eltolásakor gyakran használnak adatstruktúrát: egy kétszárnyú sor (deque). Az ötlet az, hogy az elemek indexeit csökkenő érték sorrendben tároljuk, így:

• Új elem hozzáadásakor a végéről minden kisebb elemet eltávolítunk, mivel nem lehetnek maximumok.
• Az ablak eltolásakor a sor elejéről eltávolítjuk azokat az elemeket, amelyek kimentek az ablak határain kívül.

Ez lehetővé teszi, hogy az aktuális ablak maximumát O(1) idő alatt kapjuk meg, és az egész tömböt O(n) időben dolgozzuk fel.

Python példával:

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()  # indexeket tárol
    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

# Használati példa
print(max_sliding_window([1,3,-1,-3,5,3,6,7], 3))  # [3,3,5,5,6,7]