Hoe declareer en behoud je het maximum bij het verschuiven van het venster?

Om het maximum in een venster te behouden tijdens het verschuiven van het venster, wordt vaak een datastructuur gebruikt: een dubbele queue (deque). Het idee is om de indices van de elementen op te slaan in aflopende volgorde van hun waarden, zodat:

• Bij het toevoegen van een nieuw element worden alle kleinere elementen aan het einde van de queue verwijderd, omdat ze niet het maximum kunnen zijn.
• Bij het verschuiven van het venster worden de elementen die buiten het venster vallen, verwijderd van het begin van de queue.

Dit maakt het mogelijk om het maximum in het huidige venster in O(1) te krijgen, en het hele array in O(n) te verwerken.

Voorbeeld in Python:

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()  # bewaart indices
    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

# Voorbeeld van gebruik
print(max_sliding_window([1,3,-1,-3,5,3,6,7], 3))  # [3,3,5,5,6,7]