Мы используем необходимые куки для работы сайта (вход и язык). Если ты согласишься, мы также загрузим Google Analytics, чтобы видеть, какие страницы читают, и Google reCAPTCHA для защиты форм обратной связи и сообщений об ошибке от спама. Политика конфиденциальности

← Блог
Как готовиться

Максимум в скользящем окне за O(n): монотонная очередь с разбором

· 2026-11-19

Короткий ответ. Максимум в скользящем окне за O(n) считается монотонной очередью. В деке лежат индексы, значения по ним убывают. Новый элемент выбивает с хвоста всё, что меньше него. С головы уходит то, что выпало из окна. Голова всегда хранит максимум текущего окна. Ниже устройство, код на Python, разбор и родственные задачи.

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

Дан массив и число k. Окно длины k едет слева направо. Для каждого положения нужен максимум внутри окна.

Наивно: для каждого окна пройти k элементов. Это O(n · k). При n и k в сто тысяч это десять миллиардов операций.

Монотонная очередь даёт O(n). Каждый элемент входит в дек один раз и выходит один раз.

Максимум в каждом окне из 3 чисел
maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3)
nums
1
3
-1
-3
5
3
6
7
deque (индекс:значение, начало слева, значения убывают к концу)
пусто
result
пусто

Ищем максимум в каждом окне из 3 чисел. В деке лежат индексы, чьи значения ещё могут стать максимумом.

Гонка скорости
Максимум каждых 10 подряд идущих значений в одних и тех же 40 числах

Столбики: 40 значений. Окно длиной 10, это четверть массива, и таблица ниже сохраняет эту долю.

Одна операция: одно сравнение двух значений. За каждый кадр все дорожки делают одинаковое число операций, поэтому медленная отстаёт.

Повторный просмотр каждого окна O(n·k)
операций: 0
Монотонный дек O(n)
операций: 0

 

А если чисел больше

Операции для n чисел и примерное время при 100 миллионах простых операций в секунду. Это оценка по тому же счёту, а не замер.

n = 1 000
Повторный просмотр каждого окна187 тыс. · 1,9 мс
Монотонный дек1,7 тыс. · меньше 1 мс
n = 100 000
Повторный просмотр каждого окна1,9 млрд · 19 с
Монотонный дек170 тыс. · 1,7 мс
n = 10 000 000
Повторный просмотр каждого окна18,7 трлн · 2,2 дн.
Монотонный дек17 млн · 170 мс

Страница паттерна: когда его применять и шаблон на шести языках

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

  • Дек хранит индексы. Значения по этим индексам убывают от головы к хвосту.
  • Пришёл новый элемент. Пока хвост меньше него, выкидываем хвост. Он уже никогда не будет максимумом.
  • Кладём новый индекс в хвост.
  • Голова вышла за левый край окна, убираем голову.
  • Окно заполнилось, голова это максимум.

Ключевая мысль: элемент меньше нового и старше него бесполезен. Новый переживёт его в окне и при этом больше.

Как это выглядит на примере?

Массив [1, 3, -1, -3, 5, 3, 6, 7], k = 3. Индекс 0 со значением 1: дек [0]. Индекс 1 со значением 3: 3 больше 1, выкидываем 0, дек [1]. Индекс 2 со значением -1: дек [1, 2]. Окно заполнилось, максимум 3.

Индекс 3 со значением -3: дек [1, 2, 3]. Голова 1 внутри окна 1..3, максимум 3. Индекс 4 со значением 5: выкидываем 3, 2, 1, дек [4]. Максимум 5. Дальше 5, 6, 7. Ответ [3, 3, 5, 5, 6, 7].

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

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()                    # индексы, значения убывают
    out = []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()                # хвост меньше нового, бесполезен
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()            # голова выпала из окна
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out

def min_sliding_window(nums, k):
    dq, out = deque(), []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] >= x:   # знак перевёрнут
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out

Минимум получается заменой одного знака. Всё остальное совпадает.

Нестрогое сравнение при выкидывании хвоста убирает дубликаты. Если два равных значения, старое бесполезно: новое проживёт дольше. Дек от этого короче.

Чем монотонная очередь отличается от соседних приёмов?

ПриёмЧто даётВремяКогда брать
Монотонная очередьМаксимум или минимум окнаO(n)Окно фиксированной или растущей длины
Монотонный стекБлижайший больший соседO(n)Нет окна, нужен сосед
Куча с ленивым удалениемМаксимум окнаO(n log n)Когда нужен ещё и второй максимум
Дерево отрезковМаксимум любого отрезкаO(log n) на запросОкна произвольные, массив меняется

Как решить Shortest Subarray with Sum at Least K?

Массив с отрицательными числами, нужен кратчайший подмассив с суммой не меньше k. Обычное окно ломается на отрицательных. Считаем префиксные суммы и держим дек индексов с возрастающими префиксами.

Для каждого нового префикса смотрим на голову. Разность не меньше k, запоминаем длину и убираем голову. Пока хвост не меньше нового префикса, убираем хвост. Монотонность здесь по префиксам, а не по значениям.

Как решить Constrained Subsequence Sum?

Нужна максимальная сумма подпоследовательности. Соседние индексы отличаются не больше чем на k. dp[i] равно nums[i] плюс максимум dp на последних k позициях. Этот максимум и даёт монотонная очередь. Время O(n) вместо O(n · k).

По каким словам в задаче узнать приём?

  • «Максимум в каждом окне длины k».
  • «Минимум на последних k элементах» внутри динамического программирования.
  • «Кратчайший подмассив с суммой не меньше k» при отрицательных числах.
  • «Разница между максимумом и минимумом окна не больше limit».

На каких ошибках ломается решение?

  • Хранят значения вместо индексов. Тогда не понять, выпал ли элемент из окна.
  • Выкидывают хвост только при строгом меньше. Дубликаты копятся, ответ верный, но дек растёт.
  • Проверяют голову до вставки нового элемента при k = 1 и теряют его.
  • Берут list.pop(0) вместо deque. Каждое удаление O(n).

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

Скажите: держу дек кандидатов на максимум, значения убывают. Новый элемент делает бесполезными все меньшие перед ним. Голова уходит, когда выпадает из окна.

Назовите O(n) и объясните: каждый индекс входит и выходит один раз. Потом покажите на примере из пяти чисел.

Отработать узнавание приёма можно на странице монотонная дек-очередь. Соседний приём разобран на странице монотонный стек.

Вопросы и ответы

Почему не подходит куча?

Подходит, но за O(n log n) и с ленивым удалением устаревших индексов. Дек короче в коде и линеен. Кучу берут, когда нужны несколько верхних значений.

Что делать, если окно меняется по условию, а не по длине?

Тот же дек. Левый край двигается по условию. Голова удаляется, пока её индекс меньше левого края. Так решают задачу про разницу максимума и минимума.

Можно ли держать два дека сразу?

Да. Один на максимум, другой на минимум. Оба обновляются на каждом шаге. Так считают размах окна за O(n).

Где приём встречается в реальных системах?

В мониторинге: пиковая нагрузка за последнюю минуту. В финансах: максимум цены за последние n дней. В обработке сигналов: фильтр максимума по окну.