Как оптимизировать поиск максимума в скользящем окне?

Для оптимизации поиска максимума в скользящем окне часто используют структуру данных «двусторонняя очередь» (deque). Идея в том, чтобы хранить индексы элементов в порядке убывания значений, при этом удаляя из очереди элементы, которые уже вышли за пределы окна или меньше текущего рассматриваемого элемента.

Это позволяет находить максимум в каждом окне за амортизированное O(1), а общий алгоритм работает за O(n), где n — длина массива.

Пример на Python:

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()  # хранит индексы
    result = []

    for i, num in enumerate(nums):
        # Удаляем из очереди индексы, которые вышли за пределы окна
        while dq and dq[0] <= i - k:
            dq.popleft()

        # Удаляем из очереди все элементы меньше текущего
        while dq and nums[dq[-1]] < num:
            dq.pop()

        dq.append(i)

        # Начинаем добавлять максимумы в результат, когда окно сформировано
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

# Пример использования
arr = [1,3,-1,-3,5,3,6,7]
k = 3
print(max_sliding_window(arr, k))  # Вывод: [3,3,5,5,6,7]

Такой подход значительно эффективнее наивного перебора, особенно для больших данных.