Монотонная очередь: максимум и минимум в скользящем окне за O(n)
Монотонная очередь на деке: Sliding Window Maximum за O(n), минимум в окне, окно с ограничением max − min, кратчайший подмассив с суммой ≥ K и оптимизация DP с окном. Код на Python.
Коротко
| Вопрос | Ответ |
|---|---|
| Что умеет | Очередь FIFO, которая в любой момент отдаёт свой максимум (или минимум) |
| Сложность | Амортизированно на операцию, на весь проход окна |
| Память | для окна длины |
| Главная идея | Элемент, у которого справа есть больший, никогда не станет максимумом — его можно выбросить |
| Где применяется | Sliding Window Maximum, окна с ограничением на max − min, DP вида |
- Монотонная очередь — это дек, в котором значения идут по убыванию (для максимума) или возрастанию (для минимума).
- С хвоста выбрасываем «бесперспективных» кандидатов, с головы — тех, кто вышел из окна.
- Это не то же самое, что монотонный стек: стек отвечает на «ближайший больший», очередь — на «максимум в окне, которое едет вправо».
Задача: максимум в каждом окне
LeetCode 239 Sliding Window Maximum: дан массив nums и число k. Окно длины k едет слева направо, нужно вернуть максимум каждого окна.
nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
[1 3 -1] -3 5 3 6 7 → 3
1 [3 -1 -3] 5 3 6 7 → 3
1 3 [-1 -3 5] 3 6 7 → 5
1 3 -1 [-3 5 3] 6 7 → 5
1 3 -1 -3 [5 3 6] 7 → 6
1 3 -1 -3 5 [3 6 7] → 7
Наивно считаем max каждого окна заново: . При и это миллиарды операций.
Обычное скользящее окно здесь само по себе не спасает. Сумму окна легко обновить: прибавили вошедший, вычли вышедший. С максимумом так не выйдет: если из окна ушёл текущий максимум, непонятно, кто следующий, без повторного просмотра окна. Нужна структура, которая умеет «забывать» старые элементы и при этом помнит, кто станет максимумом после них.
Решение через кучу:
Первая мысль — куча. Кладём в неё пары (-значение, индекс), а элементы, вышедшие из окна, удаляем лениво — только когда они всплыли на вершину:
import heapq def max_sliding_window_heap(nums: list[int], k: int) -> list[int]: heap = [] # (-значение, индекс) res = [] for i, x in enumerate(nums): heapq.heappush(heap, (-x, i)) while heap[0][1] <= i - k: # ленивое удаление устаревших heapq.heappop(heap) if i >= k - 1: res.append(-heap[0][0]) return res
Это и на собеседовании принимается как рабочий вариант. Но куча хранит много лишнего: элементы, которые уже никогда не станут максимумом, лежат в ней, пока их не вытолкнут. Монотонная очередь избавляется от них сразу и даёт .
Ключевое наблюдение: кого можно забыть
Возьмём два элемента окна: nums[i] и nums[j], причём i < j и nums[i] <= nums[j]. Элемент i левее, значит, он покинет окно раньше j. И пока он в окне, рядом с ним всегда есть j, который не меньше. Значит, nums[i] не будет максимумом ни в одном будущем окне. Его можно выбросить прямо сейчас.
Если выбрасывать всех таких «доминируемых» элементов, то среди оставшихся кандидатов каждый следующий (правее) строго меньше предыдущего. Получается убывающая последовательность:
- голова — самый старый и самый большой кандидат, это и есть максимум окна;
- хвост — самый свежий элемент;
- новый элемент приходит в хвост и выбрасывает всех, кто не больше него;
- когда голова выходит за левую границу окна, её снимают — и максимумом становится следующий кандидат.
Работа с обоих концов — именно для этого нужен дек.
Реализация на индексах
Хранить в деке удобнее индексы, а не значения: по индексу сразу видно, вышел ли элемент из окна.
from collections import deque def max_sliding_window(nums: list[int], k: int) -> list[int]: dq = deque() # индексы; nums[dq[0]] > nums[dq[1]] > ... res = [] 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: res.append(nums[dq[0]]) return res print(max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3)) # [3, 3, 5, 5, 6, 7]
Проверка головы — одно if, а не while: за шаг в окно входит один элемент и выходит один, поэтому устареть может максимум одна голова.
Разбор на примере
В колонке «дек» — значения по индексам из дека, чтобы было нагляднее:
i x выброшены с хвоста дек после шага ответ
0 1 — [1]
1 3 1 [3]
2 -1 — [3, -1] 3
3 -3 — [3, -1, -3] 3
4 5 -3, -1, 3 [5] 5
5 3 — [5, 3] 5
6 6 3, 5 [6] 6
7 7 6 [7] 7
На шаге i = 4 пятёрка одним махом вычищает весь дек: тройка, минус единица и минус тройка уже никогда не станут максимумом, пока рядом есть пятёрка, которая к тому же проживёт в окне дольше их.
Почему это
Внутренний while может выглядеть подозрительно, но каждый индекс попадает в дек ровно один раз и удаляется из него не более одного раза — либо с хвоста, либо с головы. Всего операций append — , всего pop и popleft — не больше . Итого на весь массив, то есть амортизированное на шаг. Это тот же аргумент, что и для монотонного стека.
Память — : в деке только индексы текущего окна.
Минимум в окне
Для минимума меняем знак сравнения: дек хранит возрастающую последовательность, с хвоста выбрасываем тех, кто не меньше нового.
def min_sliding_window(nums: list[int], k: int) -> list[int]: dq = deque() res = [] 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: res.append(nums[dq[0]]) return res print(min_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3))
[-1, -3, -3, -3, 3, 3]
### На JavaScript без настоящего дека
В JavaScript нет встроенного дека, а `Array.prototype.shift` работает за $O(n)$. Но в этой задаче дек никогда не растёт дальше `n` элементов, поэтому хватает обычного массива и двух указателей:
```javascript
function maxSlidingWindow(nums, k) {
const dq = new Array(nums.length) // индексы; вместо deque — массив и два указателя
let head = 0,
tail = 0 // живая часть: dq[head..tail-1]
const res = []
for (let i = 0; i < nums.length; i++) {
while (tail > head && nums[dq[tail - 1]] <= nums[i]) tail--
dq[tail++] = i
if (dq[head] <= i - k) head++
if (i >= k - 1) res.push(nums[dq[head]])
}
return res
}
console.log(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3)) // [ 3, 3, 5, 5, 6, 7 ]
Монотонная очередь как структура данных
Иногда окно не «длины ровно k», а с плавающими границами, как в методе двух указателей. Тогда удобно оформить очередь отдельным классом с интерфейсом обычной очереди: push в конец, pop из начала, плюс max.
class MonotonicQueue: """Очередь FIFO, которая за амортизированное O(1) отдаёт максимум.""" def __init__(self): self.q = deque() # кандидаты в максимум, по невозрастанию def push(self, x) -> None: while self.q and self.q[-1] < x: self.q.pop() self.q.append(x) def pop(self, x) -> None: # x — элемент, который сейчас уходит из головы настоящей очереди if self.q and self.q[0] == x: self.q.popleft() def max(self): return self.q[0]
Здесь хранятся значения, а не индексы, поэтому pop получает уходящий элемент и снимает голову, только если это он. Если головой был кто-то другой, значит, уходящий элемент уже был выброшен с хвоста раньше.
Обратите внимание на строгое < в push. Равные элементы не выбрасываются: если в окне две пятёрки и одна уходит, вторая должна остаться. С <= очередь на [5, 5] после ухода первой пятёрки опустела бы, а max() упал бы на пустом деке. В версии с индексами это неважно — там уход определяется по индексу, а не по значению.
Альтернатива: очередь на двух стеках
Есть и другой способ получить очередь с минимумом — собрать её из двух стеков с минимумом. В каждом стеке рядом с элементом храним минимум всего, что лежит ниже. push кладёт во входной стек, pop берёт из выходного, а если тот пуст — перекладывает в него весь входной.
class MinQueue: """Очередь на двух стеках: в каждом стеке храним пары (x, минимум ниже).""" def __init__(self): self.inbox, self.outbox = [], [] def push(self, x): m = min(x, self.inbox[-1][1]) if self.inbox else x self.inbox.append((x, m)) def pop(self): if not self.outbox: while self.inbox: x, _ = self.inbox.pop() m = min(x, self.outbox[-1][1]) if self.outbox else x self.outbox.append((x, m)) return self.outbox.pop()[0] def min(self): return min(s[-1][1] for s in (self.inbox, self.outbox) if s)
Сложность тоже амортизированная . Преимущество — работает с любой ассоциативной операцией, а не только с max/min: НОД в окне, побитовое ИЛИ, произведение матриц. Монотонная очередь так не умеет — у неё нет понятия «доминируемого» элемента для НОД. Зато для максимума и минимума дек проще и быстрее.
Задача 2: окно, где max − min не больше limit
LeetCode 1438: найти длину самого длинного подмассива, в котором разница между любыми двумя элементами не превышает limit. «Разница между любыми двумя» — это просто max − min окна.
Окно здесь переменной длины: правую границу двигаем всегда, левую — пока окно невалидно. Чтобы на каждом шаге знать и максимум, и минимум, заводим две монотонные очереди.
def longest_subarray(nums: list[int], limit: int) -> int: maxq, minq = deque(), deque() # значения: по невозрастанию / по неубыванию left = best = 0 for right, x in enumerate(nums): while maxq and maxq[-1] < x: maxq.pop() maxq.append(x) while minq and minq[-1] > x: minq.pop() minq.append(x) while maxq[0] - minq[0] > limit: out = nums[left] if maxq[0] == out: maxq.popleft() if minq[0] == out: minq.popleft() left += 1 best = max(best, right - left + 1) return best print(longest_subarray([8, 2, 4, 7], 4)) # 2 print(longest_subarray([10, 1, 2, 4, 7, 2], 5)) # 4
Каждый указатель проходит массив один раз, каждый элемент входит и выходит из каждой очереди не более одного раза — . Решение через отсортированный контейнер даёт , и разница заметна при .
Тот же шаблон с двумя очередями решает и другие задачи вида «окно, в котором разброс значений ограничен»: например, подсчёт всех таких подмассивов (LeetCode 2762 Continuous Subarrays).
Задача 3: кратчайший подмассив с суммой не меньше K
LeetCode 862 — задача уровня hard, и её часто приводят как пример, где обычное скользящее окно ломается. В массиве есть отрицательные числа, поэтому сумма окна не монотонна: расширение может её уменьшить.
Переходим к префиксным суммам: pref[j] - pref[i] >= K, нужно минимизировать j - i. Для каждого j ищем самое правое i с pref[i] <= pref[j] - K. Держим дек индексов, в котором pref строго возрастает:
- с головы: пока
pref[j] - pref[dq[0]] >= K, нашли кандидата в ответ. Голову можно снимать навсегда: любой будущийj' > jдал бы с ней только более длинный подмассив. - с хвоста: если
pref[dq[-1]] >= pref[j], хвост бесполезен —jправее и с не большим префиксом, значит, как левая граница он всегда не хуже.
def shortest_subarray(nums: list[int], k: int) -> int: n = len(nums) pref = [0] * (n + 1) for i, x in enumerate(nums): pref[i + 1] = pref[i] + x dq = deque() # индексы префиксов, pref по возрастанию best = n + 1 for j in range(n + 1): while dq and pref[j] - pref[dq[0]] >= k: best = min(best, j - dq.popleft()) while dq and pref[dq[-1]] >= pref[j]: dq.pop() dq.append(j) return best if best <= n else -1 print(shortest_subarray([2, -1, 2], 3)) # 3 print(shortest_subarray([1, 2], 4)) # -1
Здесь голова снимается не потому, что вышла из окна фиксированной длины, а потому, что больше никогда не даст лучшего ответа. Это та же идея, что и раньше: выбрасываем кандидатов, которые доминируются, — просто критерий доминирования другой.
Оптимизация DP: максимум по окну предыдущих состояний
Самое ценное применение монотонной очереди — ускорение динамического программирования, где переход выглядит так:
Наивно каждое просматривает предыдущих состояний — . Но по последним значениям — это ровно максимум в скользящем окне. Значения вычисляются слева направо, и мы кладём их в монотонную очередь по мере появления.
Jump Game VI
LeetCode 1696 — продолжение задачи о прыжках: стоим на индексе 0, за прыжок можно продвинуться на 1..k позиций, очки — сумма чисел на посещённых клетках. Нужен максимум очков на последней клетке.
def max_result(nums: list[int], k: int) -> int: n = len(nums) dp = [0] * n dp[0] = nums[0] dq = deque([0]) # индексы dp, значения dp по убыванию for i in range(1, n): if dq[0] < i - k: dq.popleft() dp[i] = nums[i] + dp[dq[0]] while dq and dp[dq[-1]] <= dp[i]: dq.pop() dq.append(i) return dp[-1] print(max_result([1, -1, -2, 4, -7, 3], 2)) # 7 print(max_result([10, -5, -2, 4, 0, 3], 3)) # 17
Обратите внимание на порядок: сначала снимаем устаревшую голову, потом читаем максимум, и только потом кладём в очередь. Если положить раньше, будет участвовать в собственном вычислении.
Constrained Subsequence Sum
LeetCode 1425: выбрать непустую подпоследовательность с максимальной суммой, в которой соседние выбранные элементы стоят не дальше чем на k друг от друга. Переход почти такой же, но предыдущее состояние можно не брать вовсе (начать подпоследовательность заново), поэтому добавляется max(0, …):
def constrained_subset_sum(nums: list[int], k: int) -> int: dp = [0] * len(nums) dq = deque() # индексы dp, значения dp по убыванию for i, x in enumerate(nums): if dq and dq[0] < i - k: dq.popleft() best_prev = dp[dq[0]] if dq else 0 dp[i] = x + max(0, best_prev) while dq and dp[dq[-1]] <= dp[i]: dq.pop() dq.append(i) return max(dp) print(constrained_subset_sum([10, 2, -10, 5, 20], 2)) # 37 print(constrained_subset_sum([-1, -2, -3], 1)) # -1
Обе задачи (medium и hard на LeetCode), в разборах решаются одинаково: «увидел по окну в переходе — поставь монотонную очередь». Тот же приём ускоряет ограниченный рюкзак с количеством копий предмета (bounded knapsack) с до : переход по каждому остатку от деления на вес предмета — тоже максимум в окне.
Как отличить от соседних приёмов
| Задача | Инструмент |
|---|---|
| Ближайший больший/меньший слева или справа | Монотонный стек |
| Максимум/минимум окна, которое едет вправо | Монотонная очередь |
| Максимум на произвольном отрезке, массив не меняется | Sparse table, на запрос |
| Максимум на отрезке с изменениями | Дерево отрезков |
| Сумма окна | Обычное окно или префиксные суммы |
Монотонная очередь работает только тогда, когда границы окна двигаются монотонно — обе только вправо. Если запросы приходят на произвольные отрезки, она бесполезна.
Типичные ошибки
Хранить значения вместо индексов и не понимать, когда снимать голову. Если в деке значения, нужен отдельный способ узнать, что голова устарела, — как в классе MonotonicQueue выше. С индексами проще и надёжнее.
<= вместо < в версии на значениях. Дубликаты выбрасываются, и при уходе одного из них очередь теряет второй. Ловится тестом [5, 5, 1] с k = 2: правильный ответ [5, 5], а такая очередь вернёт [5, 1].
Добавлять в ответ до того, как окно заполнилось. Условие i >= k - 1 — первые k - 1 шагов только накапливаем.
Неверный порядок операций в DP. Нужно: снять устаревшее → прочитать максимум → вычислить → положить с хвоста. Любая перестановка даёт ошибку на единицу в границах окна.
Использовать list.pop(0) в Python или shift() в JS. Они сдвигают весь массив, и линейное решение тихо превращается в . В Python — только collections.deque, в JS — массив с указателем головы.
Путать окно «последние k элементов» и «индексы от i−k до i−1». В Sliding Window Maximum окно включает текущий элемент, в DP — нет. Проверяйте граничное условие (<= i - k против < i - k) на маленьком примере.
Как проверить себя
Для всех задач из статьи легко написать брутфорс и сравнить на случайных данных. Для максимума в окне это одна строка:
import random for _ in range(1000): n = random.randint(1, 20) nums = [random.randint(-10, 10) for _ in range(n)] k = random.randint(1, n) brute = [max(nums[i : i + k]) for i in range(n - k + 1)] assert max_sliding_window(nums, k) == brute, (nums, k) print('ok')
Именно такой проверкой были прогнаны все функции из этой статьи, включая DP: брутфорс за против версии с очередью.
Где встречается на собеседованиях
- Sliding Window Maximum (239) — классика FAANG-собеседований. Часто ждут сначала решение на куче, потом спрашивают, можно ли за .
- Longest Continuous Subarray With Absolute Diff ≤ Limit (1438) — две очереди и два указателя.
- Shortest Subarray with Sum at Least K (862) — hard, проверяет, понимаете ли вы, почему не работает обычное окно.
- Jump Game VI (1696) и Constrained Subsequence Sum (1425) — DP с окном.
- Max Value of Equation (1499) — переписать выражение так, чтобы появился максимум по окну, и поставить очередь.
На собеседовании полезно проговорить три вещи: какие кандидаты бесполезны и почему (доминирование), какой инвариант держит дек (убывание значений, возрастание индексов) и почему сложность линейная (каждый индекс входит и выходит один раз). Этого достаточно, чтобы решение выглядело не как заученный шаблон, а как понимание.
Итого
Монотонная очередь — это дек кандидатов в максимум, из которого с хвоста уходят доминируемые элементы, а с головы — устаревшие. Она превращает «максимум каждого окна» из в и, что важнее, ускоряет целый класс DP, где переход берёт максимум по последним состояниям. Заметили в задаче «окно, которое только едет вправо» и «максимум или минимум внутри» — почти наверняка это она.