Где применяется
1. Задача
Панель мониторинга показывает пиковую задержку за последние 3 отсчёта (замера) и обновляется с каждым новым отсчётом. Окно скользит: свежий отсчёт входит справа, самый старый уходит слева, а ты сообщаешь максимум того, что внутри. Это надо делать для каждой позиции длинного потока.
Простой способ: каждый раз заново просматривать окно, то есть для каждой позиции проверять все k значений и брать наибольшее. На 1 000 000 отсчётов с окном 1000 это 1 000 000 000 сравнений. Большая их часть повторяет работу, которую уже сделали для предыдущего окна.
Для суммы в скользящем окне хватало двух действий: прибавить новое значение и вычесть ушедшее. Максимум так вычесть нельзя. Когда из окна уходит самое большое значение, следующее по величине неизвестно, пока не просмотришь окно заново. Нужна структура, которая заранее помнит претендентов на максимум по порядку.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитmaxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3)Ищем максимум в каждом окне из 3 чисел. В деке лежат индексы, чьи значения ещё могут стать максимумом.
Столбики: 40 значений. Окно длиной 10, это четверть массива, и таблица ниже сохраняет эту долю.
Одна операция: одно сравнение двух значений. За каждый кадр все дорожки делают одинаковое число операций, поэтому медленная отстаёт.
O(n·k)O(n)
Операции для n чисел и примерное время при 100 миллионах простых операций в секунду. Это оценка по тому же счёту, а не замер.
Как узнать
Эти слова в условии значат этот паттерн
- максимум или минимум каждого окна размера k
- максимум/минимум скользящего окна
- кратчайший подмассив с суммой не менее K
- нужно снимать/класть с обоих концов очереди
- дек, двусторонняя очередь
Похоже, но не то
- Монотонный стек (Monotonic stack)
Стек снимает только с вершины. Дек снимает ещё и спереди, когда значение выходит из окна.
- Скользящее окно (фиксированный размер) (Sliding window (fixed size))
Скользящая сумма переживает вычитание. Максимум нет, ради этого дек и нужен.
- Бинарная куча / очередь с приоритетом (Binary heap / priority queue)
Куча отдаёт максимум за log n. Она не умеет удалить элемент, только что вышедший из окна.
- Стек (LIFO) (Stack (LIFO))
Обычный стек не хранит порядка и открыт с одного конца. Оба ограничения тут мешают.
n до 1e6 даёт O(n), ведь каждый индекс входит и выходит один раз. Память O(k) по размеру окна.
На LeetCode
Задачи, где на каждом шаге нужен максимум или минимум скользящего окна. Дек из позиций с убывающими значениями держит ответ в начале и стоит O(n) на весь проход.
Ровно задача урока, окно фиксированной длины k и его максимум на каждом шаге.
Собери сам дек на массиве фиксированной длины с индексами головы и хвоста, которые переходят через край.
- 1438.Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit (откроется в новой вкладке)Средняя
Окно переменной длины с двумя деками, один для максимума, другой для минимума, и сужай окно, пока их разница больше limit.
Веди дек с возрастающими значениями по префиксным суммам, потому что отрицательные числа ломают обычное скользящее окно.