Kuidas deklareerida ja hoida maksimumi akna liigutamisel?

Selleks, et hoida maksimaalset väärtust aknas, kui aken liigub, kasutatakse sageli andmestruktuuri: kahemastilist järjekorda (deque). Mõte on salvestada elementide indeksid väärtuste kahanevas järjekorras, nii et:

• Uue elemendi lisamisel eemaldatakse lõpuosast kõik väiksemad elemendid, kuna need ei saa olla maksimum.
• Akna liigutamisel eemaldatakse algusest elemendid, mis on akna piiridest välja läinud.

See võimaldab saada praeguse akna maksimumi O(1) ajal ning kogu massiivi töödelda O(n) ajal.

Python näide:

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()  # salvestab indeksid
    tulemus = []
    i = 0
    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:
            tulemus.append(nums[dq[0]])
    return tulemus

# Näide kasutamiseks
print(max_sliding_window([1,3,-1,-3,5,3,6,7], 3))  # [3,3,5,5,6,7]