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

Для поддержания максимума в окне при сдвиге окна часто используют структуру данных — двунаправленную очередь (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]