---
title: "Максимум в скользящем окне за O(n): монотонная очередь с разбором"
url: https://algopath.pro/ru/blog/maksimum-v-skolzyashchem-okne
language: ru
summary: "Дек индексов с убывающими значениями держит максимум окна в голове. Шаги, разбор на примере, код на Python для максимума и минимума, родственные задачи и типичные ошибки."
updated: 2026-11-19
---

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

**Короткий ответ.** Максимум в скользящем окне за O(n) считается монотонной очередью. В деке лежат индексы, значения по ним убывают. Новый элемент выбивает с хвоста всё, что меньше него. С головы уходит то, что выпало из окна. Голова всегда хранит максимум текущего окна. Ниже устройство, код на Python, разбор и родственные задачи.

 

## Что такое максимум в скользящем окне?

 

Дан массив и число k. Окно длины k едет слева направо. Для каждого положения нужен максимум внутри окна.

 

Наивно: для каждого окна пройти k элементов. Это O(n · k). При n и k в сто тысяч это десять миллиардов операций.

 

Монотонная очередь даёт O(n). Каждый элемент входит в дек один раз и выходит один раз.

 

## Как монотонная очередь находит максимум в скользящем окне?

 

- Дек хранит индексы. Значения по этим индексам убывают от головы к хвосту.
- Пришёл новый элемент. Пока хвост меньше него, выкидываем хвост. Он уже никогда не будет максимумом.
- Кладём новый индекс в хвост.
- Голова вышла за левый край окна, убираем голову.
- Окно заполнилось, голова это максимум.

 

Ключевая мысль: элемент меньше нового и старше него бесполезен. Новый переживёт его в окне и при этом больше.

 

## Как это выглядит на примере?

 

Массив [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) и объясните: каждый индекс входит и выходит один раз. Потом покажите на примере из пяти чисел.

 

Отработать узнавание приёма можно на странице [монотонная дек-очередь](/ru/patterns/monotonic-deque). Соседний приём разобран на странице [монотонный стек](/ru/patterns/monotonic-stack).

 

## Вопросы и ответы

 

### Почему не подходит куча?

 

Подходит, но за O(n log n) и с ленивым удалением устаревших индексов. Дек короче в коде и линеен. Кучу берут, когда нужны несколько верхних значений.

 

### Что делать, если окно меняется по условию, а не по длине?

 

Тот же дек. Левый край двигается по условию. Голова удаляется, пока её индекс меньше левого края. Так решают задачу про разницу максимума и минимума.

 

### Можно ли держать два дека сразу?

 

Да. Один на максимум, другой на минимум. Оба обновляются на каждом шаге. Так считают размах окна за O(n).

 

### Где приём встречается в реальных системах?

 

В мониторинге: пиковая нагрузка за последнюю минуту. В финансах: максимум цены за последние n дней. В обработке сигналов: фильтр максимума по окну.
