---
title: "Монотонная дек-очередь (максимум/минимум окна)"
url: https://algopath.pro/ru/patterns/monotonic-deque
language: ru
summary: "Дек, упорядоченный так, что спереди всегда лежит максимум окна. Проигравшие значения уходят сзади, а устаревшие спереди."
updated: 2026-08-24
---

# Монотонная дек-очередь (максимум/минимум окна)

Дек, упорядоченный так, что спереди всегда лежит максимум окна. Проигравшие значения уходят сзади, а устаревшие спереди.

## Монотонная дек-очередь (максимум/минимум окна): как это работает?

Дек хранит индексы, а не значения. Индекс говорит, когда элемент выйдет из окна.

Перед вставкой нового индекса снимите сзади все индексы с меньшим значением. Они уже никогда не станут максимумом.

Положите новый индекс в конец. Значения теперь убывают от начала к концу.

Посмотрите на передний индекс. Если он выехал из окна, уберите его.

Теперь спереди лежит максимум окна. Читайте его без всякого перебора.

Каждый индекс кладётся один раз и снимается один раз. Именно это держит проход линейным.

- `дек = [0]` Окно из 3 по массиву [1, 3, -1, -3, 5]. Индекс 0 входит.
- `дек = [1]` Тройка бьёт стоящую сзади единицу. Индекс 0 снимается с конца.
- `дек = [1, 2]` -1 меньше, поэтому остаётся. Окно заполнено, максимум равен 3.
- `дек = [1, 2, 3]` -3 снова меньше. Передний индекс всё ещё в окне.
- `дек = [4]` Пятёрка бьёт всех и опустошает дек. Максимум равен 5.

## Монотонная дек-очередь (максимум/минимум окна): когда применять?

- максимум или минимум каждого окна размера k
- максимум/минимум скользящего окна
- кратчайший подмассив с суммой не менее K
- нужно снимать/класть с обоих концов очереди
- дек, двусторонняя очередь

## Монотонная дек-очередь (максимум/минимум окна): с чем путают?

- **Монотонный стек** - Стек снимает только с вершины. Дек снимает ещё и спереди, когда значение выходит из окна.
- **Скользящее окно (фиксированный размер)** - Скользящая сумма переживает вычитание. Максимум нет, ради этого дек и нужен.
- **Бинарная куча / очередь с приоритетом** - Куча отдаёт максимум за log n. Она не умеет удалить элемент, только что вышедший из окна.
- **Стек (LIFO)** - Обычный стек не хранит порядка и открыт с одного конца. Оба ограничения тут мешают.

## Монотонная дек-очередь (максимум/минимум окна): сложность по времени и памяти

n до 1e6 даёт O(n), ведь каждый индекс входит и выходит один раз. Память O(k) по размеру окна.

## Монотонная дек-очередь (максимум/минимум окна): разбор примера

### Самый длинный отрезок в пределах лимита

Найдите самый длинный отрезок, где наибольшее и наименьшее значения различаются не больше чем на лимит.

Отрезок должен быть непрерывным.

Растите переменное окно и держите два дека: для максимумов и для минимумов.

Когда два передних значения расходятся больше лимита, сужайте слева. Передний индекс убирайте, как только он устарел.

```javascript
function longestSubarray(nums, limit) {
    const maxQ = []; // indices, values falling from front to back
    const minQ = []; // indices, values rising from front to back
    let left = 0;
    let best = 0;

    for (let right = 0; right < nums.length; right++) {
        while (maxQ.length && nums[maxQ[maxQ.length - 1]] <= nums[right]) maxQ.pop();
        while (minQ.length && nums[minQ[minQ.length - 1]] >= nums[right]) minQ.pop();
        maxQ.push(right);
        minQ.push(right);

        while (nums[maxQ[0]] - nums[minQ[0]] > limit) {
            if (maxQ[0] === left) maxQ.shift();
            if (minQ[0] === left) minQ.shift();
            left++;
        }

        best = Math.max(best, right - left + 1);
    }

    return best;
}
```

## Монотонная дек-очередь (максимум/минимум окна): частые ошибки

- **Хранят значения вместо индексов** Без индекса не понять, когда элемент устарел. Кладите позицию и читайте значение по ней.
- **Подрезают перед вставкой не тот конец** Порядок здесь важен. Сначала снимите проигравших сзади, потом проверьте начало.
- **Небрежно обходятся с равными значениями** Снимать ли при равенстве, решает, какой из дубликатов выживет. Это важно, когда ответ это индекс.
- **Берут кучу вместо дека** Куча не умеет удалить элемент, только что вышедший из окна. Её удаления ленивые и стоят лишнего.

## Монотонная дек-очередь (максимум/минимум окна): задачи с собеседований

- **Максимум скользящего окна** Чистая форма: читайте начало на каждом шаге.
- **Отрезок с разбросом в пределах лимита** Два дека, по одному на каждый край.
- **Кратчайший подмассив с суммой не меньше k** Префиксные суммы и возрастающий дек по ним.
- **Прыжки VI** Лучший результат внутри достижимого окна.
- **Сумма подпоследовательности с ограничением** То же окно, но по массиву динамики.
- **Максимум значения уравнения** Окно по x с ключом y минус x.
- **Минимум скользящего окна** Тот же код с перевёрнутым сравнением.

## JavaScript

```javascript
function maxSlidingWindow(nums, k) {
    const deque = []; // stores indices, values decreasing
    const result = [];
    for (let i = 0; i < nums.length; i++) {
        while (deque.length && deque[0] <= i - k) deque.shift();
        while (deque.length && nums[deque[deque.length - 1]] < nums[i]) deque.pop();
        deque.push(i);
        if (i >= k - 1) result.push(nums[deque[0]]);
    }
    return result;
}
```

## Python

```python
from collections import deque as dq

def max_sliding_window(nums, k):
    d = dq()  # indices, values decreasing
    result = []
    for i, x in enumerate(nums):
        while d and d[0] <= i - k:
            d.popleft()
        while d and nums[d[-1]] < x:
            d.pop()
        d.append(i)
        if i >= k - 1:
            result.append(nums[d[0]])
    return result
```

## PHP

```php
function maxSlidingWindow(array $nums, int $k): array {
    $deque = []; // indices, values decreasing
    $result = [];
    foreach ($nums as $i => $x) {
        while ($deque && $deque[0] <= $i - $k) array_shift($deque);
        while ($deque && $nums[end($deque)] < $x) array_pop($deque);
        $deque[] = $i;
        if ($i >= $k - 1) $result[] = $nums[$deque[0]];
    }
    return $result;
}
```