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

Монотонная очередь на деке: Sliding Window Maximum за O(n), минимум в окне, окно с ограничением max − min, кратчайший подмассив с суммой ≥ K и оптимизация DP с окном. Код на Python.

16 мин чтенияалгоритмы · очередь · скользящее окно · динамическое программирование

Коротко

ВопросОтвет
Что умеетОчередь FIFO, которая в любой момент отдаёт свой максимум (или минимум)
СложностьАмортизированно O(1)O(1) на операцию, O(n)O(n) на весь проход окна
ПамятьO(k)O(k) для окна длины kk
Главная идеяЭлемент, у которого справа есть больший, никогда не станет максимумом — его можно выбросить
Где применяетсяSliding Window Maximum, окна с ограничением на max − min, DP вида dp[i]=f(max⁡dp[i−k..i−1])dp[i] = f(\max dp[i-k..i-1])
  • Монотонная очередь — это дек, в котором значения идут по убыванию (для максимума) или возрастанию (для минимума).
  • С хвоста выбрасываем «бесперспективных» кандидатов, с головы — тех, кто вышел из окна.
  • Это не то же самое, что монотонный стек: стек отвечает на «ближайший больший», очередь — на «максимум в окне, которое едет вправо».

Задача: максимум в каждом окне

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 каждого окна заново: O(n⋅k)O(n \cdot k). При n=105n = 10^5 и k=5⋅104k = 5 \cdot 10^4 это миллиарды операций.

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

Решение через кучу: O(nlog⁡n)O(n \log n)

Первая мысль — куча. Кладём в неё пары (-значение, индекс), а элементы, вышедшие из окна, удаляем лениво — только когда они всплыли на вершину:

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

Это O(nlog⁡n)O(n \log n) и на собеседовании принимается как рабочий вариант. Но куча хранит много лишнего: элементы, которые уже никогда не станут максимумом, лежат в ней, пока их не вытолкнут. Монотонная очередь избавляется от них сразу и даёт O(n)O(n).

Ключевое наблюдение: кого можно забыть

Возьмём два элемента окна: 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 пятёрка одним махом вычищает весь дек: тройка, минус единица и минус тройка уже никогда не станут максимумом, пока рядом есть пятёрка, которая к тому же проживёт в окне дольше их.

Почему это O(n)O(n)

Внутренний while может выглядеть подозрительно, но каждый индекс попадает в дек ровно один раз и удаляется из него не более одного раза — либо с хвоста, либо с головы. Всего операций append — nn, всего pop и popleft — не больше nn. Итого O(n)O(n) на весь массив, то есть амортизированное O(1)O(1) на шаг. Это тот же аргумент, что и для монотонного стека.

Память — O(k)O(k): в деке только индексы текущего окна.

Минимум в окне

Для минимума меняем знак сравнения: дек хранит возрастающую последовательность, с хвоста выбрасываем тех, кто не меньше нового.

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)

Сложность тоже амортизированная O(1)O(1). Преимущество — работает с любой ассоциативной операцией, а не только с 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

Каждый указатель проходит массив один раз, каждый элемент входит и выходит из каждой очереди не более одного раза — O(n)O(n). Решение через отсортированный контейнер даёт O(nlog⁡n)O(n \log n), и разница заметна при n=105n = 10^5.

Тот же шаблон с двумя очередями решает и другие задачи вида «окно, в котором разброс значений ограничен»: например, подсчёт всех таких подмассивов (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: максимум по окну предыдущих состояний

Самое ценное применение монотонной очереди — ускорение динамического программирования, где переход выглядит так:

dp[i]=nums[i]+max⁡i−k≤j<idp[j]dp[i] = nums[i] + \max_{i-k \le j < i} dp[j]

Наивно каждое dp[i]dp[i] просматривает kk предыдущих состояний — O(n⋅k)O(n \cdot k). Но max⁡\max по последним kk значениям dpdp — это ровно максимум в скользящем окне. Значения dpdp вычисляются слева направо, и мы кладём их в монотонную очередь по мере появления.

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

Обратите внимание на порядок: сначала снимаем устаревшую голову, потом читаем максимум, и только потом кладём dp[i]dp[i] в очередь. Если положить раньше, dp[i]dp[i] будет участвовать в собственном вычислении.

Constrained Subsequence Sum

LeetCode 1425: выбрать непустую подпоследовательность с максимальной суммой, в которой соседние выбранные элементы стоят не дальше чем на k друг от друга. Переход почти такой же, но предыдущее состояние можно не брать вовсе (начать подпоследовательность заново), поэтому добавляется max(0, …):

dp[i]=nums[i]+max⁡(0,max⁡i−k≤j<idp[j])dp[i] = nums[i] + \max\left(0, \max_{i-k \le j < i} dp[j]\right)
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), в разборах решаются одинаково: «увидел max⁡\max по окну в переходе — поставь монотонную очередь». Тот же приём ускоряет ограниченный рюкзак с количеством копий предмета (bounded knapsack) с O(n⋅W⋅c)O(n \cdot W \cdot c) до O(n⋅W)O(n \cdot W): переход по каждому остатку от деления на вес предмета — тоже максимум в окне.

Как отличить от соседних приёмов

ЗадачаИнструмент
Ближайший больший/меньший слева или справаМонотонный стек
Максимум/минимум окна, которое едет вправоМонотонная очередь
Максимум на произвольном отрезке, массив не меняетсяSparse table, O(1)O(1) на запрос
Максимум на отрезке с изменениямиДерево отрезков
Сумма окнаОбычное окно или префиксные суммы

Монотонная очередь работает только тогда, когда границы окна двигаются монотонно — обе только вправо. Если запросы приходят на произвольные отрезки, она бесполезна.

Типичные ошибки

Хранить значения вместо индексов и не понимать, когда снимать голову. Если в деке значения, нужен отдельный способ узнать, что голова устарела, — как в классе MonotonicQueue выше. С индексами проще и надёжнее.

<= вместо < в версии на значениях. Дубликаты выбрасываются, и при уходе одного из них очередь теряет второй. Ловится тестом [5, 5, 1] с k = 2: правильный ответ [5, 5], а такая очередь вернёт [5, 1].

Добавлять в ответ до того, как окно заполнилось. Условие i >= k - 1 — первые k - 1 шагов только накапливаем.

Неверный порядок операций в DP. Нужно: снять устаревшее → прочитать максимум → вычислить dp[i]dp[i] → положить dp[i]dp[i] с хвоста. Любая перестановка даёт ошибку на единицу в границах окна.

Использовать list.pop(0) в Python или shift() в JS. Они сдвигают весь массив, и линейное решение тихо превращается в O(n⋅k)O(n \cdot k). В 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: брутфорс за O(n⋅k)O(n \cdot k) против версии с очередью.

Где встречается на собеседованиях

  • Sliding Window Maximum (239) — классика FAANG-собеседований. Часто ждут сначала решение на куче, потом спрашивают, можно ли за O(n)O(n).
  • 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) — переписать выражение так, чтобы появился максимум по окну, и поставить очередь.

На собеседовании полезно проговорить три вещи: какие кандидаты бесполезны и почему (доминирование), какой инвариант держит дек (убывание значений, возрастание индексов) и почему сложность линейная (каждый индекс входит и выходит один раз). Этого достаточно, чтобы решение выглядело не как заученный шаблон, а как понимание.

Итого

Монотонная очередь — это дек кандидатов в максимум, из которого с хвоста уходят доминируемые элементы, а с головы — устаревшие. Она превращает «максимум каждого окна» из O(n⋅k)O(n \cdot k) в O(n)O(n) и, что важнее, ускоряет целый класс DP, где переход берёт максимум по последним kk состояниям. Заметили в задаче «окно, которое только едет вправо» и «максимум или минимум внутри» — почти наверняка это она.

Потренироваться в спокойной обстановке

Все задачи