---
title: "Монотонный стек"
url: https://algopath.pro/ru/patterns/monotonic-stack
language: ru
summary: "Держите значения в стеке возрастающими снизу вверх. Снимайте всё, что проигрывает новому, и каждое снятие находит ответ."
updated: 2026-08-24
---

# Монотонный стек

Держите значения в стеке возрастающими снизу вверх. Снимайте всё, что проигрывает новому, и каждое снятие находит ответ.

## Монотонный стек: как это работает?

Стек хранит индексы, а не значения. Каждый индекс ждёт там своего ответа.

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

Направление сравнения решает результат. Снимайте, пока верхушка меньше, и получите следующий больший.

Разверните сравнение на «пока верхушка больше». Так получается следующий меньший.

Всё, что осталось в стеке, ответа не нашло. У этих позиций остаётся значение по умолчанию.

Внутренний цикл выглядит квадратичным. Каждый индекс входит и выходит по разу, поэтому итог линейный.

- `[0]` Кладём индекс 0. Значение 2 лежит в стеке.
- `[0, 1]` Значение 1 проигрывает двойке. Снимать нечего, кладём индекс 1.
- `[2]` Значение 5 бьёт 1, затем 2. Оба снимаются с ответом 5.
- `[2, 3]` Значение 3 проигрывает пятёрке. Кладём индекс 3.
- `[2, 3]` Вход кончился. У индексов 2 и 3 остаётся -1.

## Монотонный стек: когда применять?

- ближайший больший / ближайший меньший элемент
- сколько дней ждать потепления
- наибольший прямоугольник в гистограмме
- сколько воды соберётся между столбиками
- отрезок/серия, заканчивающаяся первым большим или меньшим значением

## Монотонный стек: с чем путают?

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

## Монотонный стек: сложность по времени и памяти

n до 1e5 элементов даёт O(n). Каждый элемент кладут один раз и снимают не больше раза.

## Монотонный стек: разбор примера

### Температура по дням

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

Если тёплого дня нет, ответ 0. Вложенные циклы дают O(n в квадрате) и не проходят по времени.

Это тот же следующий больший элемент, только нужна дистанция вместо значения.

Идём слева направо. Снимаем каждый день в стеке, который холоднее сегодняшнего.

Сегодня и есть его первый тёплый день. Ожидание равно разнице индексов.

Дни, оставшиеся в стеке, тепла не дождались. У них остаётся 0.

```javascript
function dailyTemperatures(temps) {
    const wait = new Array(temps.length).fill(0);
    const stack = []; // indices, coldest at the bottom

    for (let today = 0; today < temps.length; today++) {
        while (
            stack.length &&
            temps[stack[stack.length - 1]] < temps[today]
        ) {
            const colder = stack.pop();
            wait[colder] = today - colder;
        }
        stack.push(today);
    }

    return wait; // days still on the stack keep their 0
}
```

## Монотонный стек: частые ошибки

- **Кладут значения вместо индексов** Для расстояния нужна позиция. Кладите индекс, а значение берите как temps[i].
- **Путают направление сравнения** Меньше на верхушке даёт следующий больший. Больше на верхушке даёт следующий меньший.
- **Забывают про остаток стека** Элементы, оставшиеся в стеке, ответа не нашли. Решите заранее: -1, 0 или длина массива.
- **Неверно обрабатывают равные значения** Строгое < оставляет дубликаты в стеке, <= снимает их. Проверьте на [2, 2, 2].

## Монотонный стек: задачи с собеседований

- **Следующий больший элемент** Паттерн без маскировки. Остальные задачи переформулируют его.
- **Температура по дням** Тот же следующий больший, но спрашивают дистанцию.
- **Наибольший прямоугольник в гистограмме** Каждому столбцу нужен первый меньший сосед с обеих сторон.
- **Сбор дождевой воды** Вода стоит между столбцом и следующим более высоким.
- **Биржевой спан** Следующий больший в обратную сторону, со счётом дней.
- **Удалить k цифр** Снимаем большие цифры, чтобы осталось наименьшее число.
- **Сумма минимумов подмассивов** Каждое значение владеет отрезком между меньшими соседями.

## JavaScript

```javascript
function nextGreater(nums) {
    const result = new Array(nums.length).fill(-1);
    const stack = [];
    for (let i = 0; i < nums.length; i++) {
        while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
            result[stack.pop()] = nums[i];
        }
        stack.push(i);
    }
    return result;
}
```

## Python

```python
def next_greater(nums):
    result = [-1] * len(nums)
    stack = []
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            result[stack.pop()] = x
        stack.append(i)
    return result
```

## PHP

```php
function nextGreater(array $nums): array {
    $result = array_fill(0, count($nums), -1);
    $stack = [];
    foreach ($nums as $i => $x) {
        while ($stack && $nums[end($stack)] < $x) {
            $result[array_pop($stack)] = $x;
        }
        $stack[] = $i;
    }
    return $result;
}
```