Максимум в скользящем окне за O(n): монотонная очередь с разбором
Elman Huseynov · 2026-11-19
Короткий ответ. Максимум в скользящем окне за O(n) считается монотонной очередью. В деке лежат индексы, значения по ним убывают. Новый элемент выбивает с хвоста всё, что меньше него. С головы уходит то, что выпало из окна. Голова всегда хранит максимум текущего окна. Ниже устройство, код на Python, разбор и родственные задачи.
Что такое максимум в скользящем окне?
Дан массив и число k. Окно длины k едет слева направо. Для каждого положения нужен максимум внутри окна.
Наивно: для каждого окна пройти k элементов. Это O(n · k). При n и k в сто тысяч это десять миллиардов операций.
Монотонная очередь даёт O(n). Каждый элемент входит в дек один раз и выходит один раз.
maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3)Ищем максимум в каждом окне из 3 чисел. В деке лежат индексы, чьи значения ещё могут стать максимумом.
Столбики: 40 значений. Окно длиной 10, это четверть массива, и таблица ниже сохраняет эту долю.
Одна операция: одно сравнение двух значений. За каждый кадр все дорожки делают одинаковое число операций, поэтому медленная отстаёт.
O(n·k)O(n)
Операции для n чисел и примерное время при 100 миллионах простых операций в секунду. Это оценка по тому же счёту, а не замер.
Страница паттерна: когда его применять и шаблон на шести языках
Как монотонная очередь находит максимум в скользящем окне?
- Дек хранит индексы. Значения по этим индексам убывают от головы к хвосту.
- Пришёл новый элемент. Пока хвост меньше него, выкидываем хвост. Он уже никогда не будет максимумом.
- Кладём новый индекс в хвост.
- Голова вышла за левый край окна, убираем голову.
- Окно заполнилось, голова это максимум.
Ключевая мысль: элемент меньше нового и старше него бесполезен. Новый переживёт его в окне и при этом больше.
Как это выглядит на примере?
Массив [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 дней. В обработке сигналов: фильтр максимума по окну.