Как да обявите и поддържате максимум при преместване на прозореца?

За да поддържате максимум в прозорец при преместване на прозореца, често се използва структура от данни: двупосочна опашка (deque). Идеята е да се съхраняват индексите на елементите в низходящ ред по стойностите им, така че:

• При добавяне на нов елемент, се премахват от края на опашката всички по-малки елементи, тъй като те не могат да бъдат максимум.
• При преместване на прозореца, се премахват от началото на опашката елементите, които са излезли извън границите на прозореца.

Това позволява да се получи максимумът в текущия прозорец за O(1), а цялата масивна обработка за O(n).

Пример на Python:

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()  # съхранява индекси
    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

# Пример за използване
print(max_sliding_window([1,3,-1,-3,5,3,6,7], 3))  # [3,3,5,5,6,7]