Максимум в скользящем окне с деком
Храните экстремальные значения окна за O(n)
«Максимум в скользящем окне с деком» — бесплатный урок Competitive Programming Academy на CoddyKit. Это урок 4 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Competitive Programming Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Competitive Programming Academy содержит 4 уроков всего.
Максимум в скользящем окне
Дан массив и размер окна k. Нужно найти максимум в каждом окне при его сдвиге вправо. Наивное решение работает за O(n, умноженное на k).
Более быстрое решение
С помощью монотонной двусторонней очереди можно найти ответ для каждого окна за общее время O(n), просмотрев массив всего один раз.
Снова храните индексы
Храните в двусторонней очереди индексы, а не значения. Индексы позволяют проверить, вышел ли первый элемент за пределы текущего окна.
from collections import deque
dq = deque()
res = []Поддерживайте убывающий порядок
Двусторонняя очередь хранит элементы в порядке убывания значений от начала к концу, поэтому первый индекс всегда указывает на максимум окна.
Удаляйте меньшие элементы с конца
Перед добавлением индекса i извлекайте элементы с конца, пока их значения меньше, поскольку в будущем они уже не смогут стать максимумом.
while dq and nums[dq[-1]] <= nums[i]:
dq.pop()Добавьте новый индекс
После удаления слабых элементов с конца добавьте текущий индекс. Порядок в двусторонней очереди останется правильным для следующих шагов.
dq.append(i)Удалите устаревший первый элемент
Если первый индекс вышел за пределы окна, удалите его с помощью popleft. Окно размера k начинается с индекса i минус k плюс один.
if dq[0] <= i - k:
dq.popleft()Записывайте каждый максимум
После формирования первого полного окна на индексе k минус один начальный элемент двусторонней очереди содержит ответ для каждой следующей позиции.
if i >= k - 1:
res.append(nums[dq[0]])Следите за порядком удаления
Удаляйте устаревший первый элемент до чтения ответа. Иначе Вы можете сообщить максимум, который уже вышел из окна.
Почему сохраняется линейное время
Каждый индекс добавляется и удаляется не более одного раза, поэтому работа с двусторонней очередью занимает амортизированно O(1) на шаг и O(n) в целом.
Минимум в окне — та же идея
Для минимума в скользящем окне поддерживайте возрастающий порядок в двусторонней очереди. Просто измените сравнение при удалении элементов с конца.
while dq and nums[dq[-1]] >= nums[i]:
dq.pop()Быстрая проверка
Что хранит начало монотонной двусторонней очереди при поиске максимума в скользящем окне?
Итоги: двусторонняя очередь побеждает в задачах с окнами
Вы поддерживали убывающую двустороннюю очередь индексов: удаляли маленькие элементы с конца, убирали устаревший первый элемент и читали начало, чтобы получить максимум каждого окна за O(n). 🏆
Часто задаваемые вопросы
Урок «Максимум в скользящем окне с деком» бесплатный?
Да — полный текст урока «Максимум в скользящем окне с деком» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Competitive Programming Academy, подпишись на CoddyKit PRO. Курс Competitive Programming Academy содержит 4 уроков всего.
Чему я научусь в уроке «Максимум в скользящем окне с деком»?
Храните экстремальные значения окна за O(n) Ты практикуешь Competitive Programming Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Competitive Programming Academy?
Предыдущий опыт не требуется. Competitive Programming Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 4 из 4.
Сколько времени занимает урок «Максимум в скользящем окне с деком»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Competitive Programming Academy?
Да. Каждый урок Competitive Programming Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Стеки для сопоставления скобок
- Монотонный стек: следующий больший элемент
- Очереди и collections.deque
- Максимум в скользящем окне с деком