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

Монотонный стек простыми словами: как за один проход ответить «когда впервые станет больше», почему время линейное при вложенном цикле, монотонная очередь на деке в Java, Go, JavaScript и Python.

Опубликовано 24 августа 2026 обновлено 30 сентября 2026 ~16 мин чтения

← назад к разделу

Мы уже знаем стек как структуру «последним пришёл — первым ушёл». Оказывается, если поддерживать в стеке упорядоченность, он решает целый класс задач, которые иначе требуют вложенных циклов.

Речь о вопросах вида: «для каждого дня — через сколько дней впервые будет выручка больше?», «какой ближайший столбец слева выше этого?».

Проблема

Возьмём выручку по дням и для каждого дня найдём, через сколько дней она впервые станет больше. Наивное решение — для каждого дня бежать вперёд, пока не встретим больший:

for (int i = 0; i < revenue.length; i++) {
    for (int j = i + 1; j < revenue.length; j++) {
        if (revenue[j] > revenue[i]) { answer[i] = j - i; break; }
    }
}

for i := 0; i < len(revenue); i++ {
	for j := i + 1; j < len(revenue); j++ {
		if revenue[j] > revenue[i] {
			answer[i] = j - i
			break
		}
	}
}

for (let i = 0; i < revenue.length; i++) {
  for (let j = i + 1; j < revenue.length; j++) {
    if (revenue[j] > revenue[i]) { answer[i] = j - i; break; }
  }
}

for i in range(len(revenue)):
    for j in range(i + 1, len(revenue)):
        if revenue[j] > revenue[i]:
            answer[i] = j - i
            break

Это O(N²). Причём работа делается многократно: если выручка долго падает, каждый день заново пробегает один и тот же хвост.

Идея: очередь ожидающих

Заметим: пока выручка падает, каждый новый день ничем не помогает предыдущим — он ведь меньше. Все они «ждут» дня, который окажется выше. А когда такой день наконец приходит, он закрывает сразу всех, кто ниже него.

Значит, нужно хранить дни, которые ещё ждут своего роста. И хранить их удобно стеком: последний пришедший — самый свежий и самый низкий, он же и закроется первым.

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

В стеке лежат индексы, а не значения: индекс позволяет и достать выручку, и посчитать расстояние в днях. Дни, оставшиеся в стеке в конце, так и не дождались роста — у них в ответе ноль, и он уже там, потому что массив ответов создан заполненным нулями.

живой пример

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class DaysToGrow {
    public static void main(String[] args) {
        int[] revenue = {70, 60, 50, 90, 80, 120};
        int[] answer = new int[revenue.length];
        Deque<Integer> waiting = new ArrayDeque<>();
        int pops = 0;
        for (int i = 0; i < revenue.length; i++) {
            while (!waiting.isEmpty() && revenue[i] > revenue[waiting.peek()]) {
                int day = waiting.pop();
                answer[day] = i - day;
                pops++;
            }
            waiting.push(i);
        }
        System.out.println("выручка: " + Arrays.toString(revenue));
        System.out.println("ждать:   " + Arrays.toString(answer));
        System.out.println("снятий со стека: " + pops + " на " + revenue.length + " дней");
    }
}

Запустить

Запуск примеров доступен в платном доступе. Там этот же код выполняется прямо в статье: редактор, запуск и проверка рядом с абзацем. Три дня бесплатно →

живой пример

package main

import "fmt"

func main() {
	revenue := []int{70, 60, 50, 90, 80, 120}
	answer := make([]int, len(revenue))
	var waiting []int
	pops := 0
	for i := range revenue {
		for len(waiting) > 0 && revenue[i] > revenue[waiting[len(waiting)-1]] {
			day := waiting[len(waiting)-1]
			waiting = waiting[:len(waiting)-1]
			answer[day] = i - day
			pops++
		}
		waiting = append(waiting, i)
	}
	fmt.Println("выручка:", revenue)
	fmt.Println("ждать:  ", answer)
	fmt.Printf("снятий со стека: %d на %d дней\n", pops, len(revenue))
}

Запустить

живой пример

const revenue = [70, 60, 50, 90, 80, 120];
const answer = new Array(revenue.length).fill(0);
const waiting = [];
let pops = 0;
for (let i = 0; i < revenue.length; i++) {
  while (waiting.length > 0 && revenue[i] > revenue[waiting.at(-1)]) {
    const day = waiting.pop();
    answer[day] = i - day;
    pops++;
  }
  waiting.push(i);
}
console.log("выручка:", revenue);
console.log("ждать:  ", answer);
console.log(`снятий со стека: ${pops} на ${revenue.length} дней`);

Запустить

живой пример

revenue = [70, 60, 50, 90, 80, 120]
answer = [0] * len(revenue)
waiting: list[int] = []
pops = 0
for i, value in enumerate(revenue):
    while waiting and value > revenue[waiting[-1]]:
        day = waiting.pop()
        answer[day] = i - day
        pops += 1
    waiting.append(i)
print("выручка:", revenue)
print("ждать:  ", answer)
print(f"снятий со стека: {pops} на {len(revenue)} дней")

Запустить

Стек здесь монотонный: сверху вниз выручка в нём возрастает. Каждый новый день перед добавлением «срезает» всё, что ниже его.

Дни, оставшиеся в стеке в конце, обрабатывают отдельным проходом или, чтобы прохода не было, дописывают в конец массива стража: значение заведомо больше всех. Страж на последнем шаге выталкивает всех, кто ещё ждёт, и стек опустошается сам; ответ для них потом заменяют на «не дождались». Тот же приём делает симметричную задачу: чтобы искать ближайший меньший, знак сравнения переворачивают на <, и стек становится убывающим сверху вниз, а каждый новый день срезает всё, что выше него; логика та же, монотонность другая.

Почему это линейно, хотя внутри цикл

Смущает while внутри for — выглядит как O(N²). Но посчитаем не итерации, а операции со стеком: каждый день кладётся в стек ровно один раз и снимается не больше одного раза. Это и печатает счётчик pops: на шести днях снятий пять, и больше шести их не станет.

Такой способ считать называется амортизированной оценкой: отдельный шаг бывает дорогим, но общая работа ограничена. Итог — O(N) по времени и O(N) по памяти в худшем случае, когда данные монотонно убывают и никто не закрывается до самого конца.

Строгое или нестрогое сравнение

В коде стоит revenue[i] > revenue[waiting.peek()] — строго больше. Это не мелочь: на данных с повторами два варианта расходятся сразу.

живой пример

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class StrictOrNot {
    public static void main(String[] args) {
        System.out.println("строго  >  : " + days(true));
        System.out.println("нестрого >=: " + days(false));
    }

    static String days(boolean strict) {
        int[] revenue = {5, 5, 5};
        int[] answer = new int[revenue.length];
        Deque<Integer> waiting = new ArrayDeque<>();
        for (int i = 0; i < revenue.length; i++) {
            while (!waiting.isEmpty() && (strict
                    ? revenue[i] > revenue[waiting.peek()]
                    : revenue[i] >= revenue[waiting.peek()])) {
                int day = waiting.pop();
                answer[day] = i - day;
            }
            waiting.push(i);
        }
        return Arrays.toString(answer);
    }
}

Запустить

живой пример

package main

import "fmt"

func days(strict bool) []int {
	revenue := []int{5, 5, 5}
	answer := make([]int, len(revenue))
	var waiting []int
	for i := range revenue {
		for len(waiting) > 0 {
			top := revenue[waiting[len(waiting)-1]]
			closes := revenue[i] > top
			if !strict {
				closes = revenue[i] >= top
			}
			if !closes {
				break
			}
			day := waiting[len(waiting)-1]
			waiting = waiting[:len(waiting)-1]
			answer[day] = i - day
		}
		waiting = append(waiting, i)
	}
	return answer
}

func main() {
	fmt.Println("строго  >  :", days(true))
	fmt.Println("нестрого >=:", days(false))
}

Запустить

живой пример

function days(strict) {
  const revenue = [5, 5, 5];
  const answer = new Array(revenue.length).fill(0);
  const waiting = [];
  for (let i = 0; i < revenue.length; i++) {
    while (waiting.length > 0 && (strict
      ? revenue[i] > revenue[waiting.at(-1)]
      : revenue[i] >= revenue[waiting.at(-1)])) {
      const day = waiting.pop();
      answer[day] = i - day;
    }
    waiting.push(i);
  }
  return JSON.stringify(answer);
}

console.log("строго  >  :", days(true));
console.log("нестрого >=:", days(false));

Запустить

живой пример

def days(strict: bool) -> list[int]:
    revenue = [5, 5, 5]
    answer = [0] * len(revenue)
    waiting: list[int] = []
    for i, value in enumerate(revenue):
        while waiting and (value > revenue[waiting[-1]] if strict else value >= revenue[waiting[-1]]):
            day = waiting.pop()
            answer[day] = i - day
        waiting.append(i)
    return answer


print("строго  >  :", days(True))
print("нестрого >=:", days(False))

Запустить

При >= равные значения начинают закрывать друг друга: на {5, 5, 5} первый день получает ответ «через один день», хотя роста не было — выручка осталась той же. Выбор определяется формулировкой: «строго больше» или «не меньше». Это самое частое место ошибки в приёме.

Направление тоже настраивается: чтобы искать ближайший больший слева, идут по массиву справа налево; чтобы искать меньший — переворачивают знак сравнения.

Монотонная очередь

Родственный приём — когда нужен максимум в скользящем окне. Стека уже мало: элементы уходят не только сверху (их вытеснил больший), но и снизу (они выпали из окна). Берут очередь с доступом с обоих концов — дек:

с хвоста убирают всех, кто меньше нового элемента (они больше никогда не станут максимумом);
с головы убирают тех, кто вышел за левый край окна;
максимум окна всегда лежит в голове.

Время тоже O(N) и по той же причине: каждый элемент входит и выходит по разу.

Один шаг скользящего окна целиком: смотрите на два места чистки - хвост режет новый элемент, голову режет левый край окна.

живой пример

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class WindowMax {
    public static void main(String[] args) {
        int[] load = {3, 1, 4, 1, 5, 9, 2, 6};
        int k = 3;
        int[] max = new int[load.length - k + 1];
        Deque<Integer> dq = new ArrayDeque<>();
        for (int i = 0; i < load.length; i++) {
            while (!dq.isEmpty() && load[dq.peekLast()] <= load[i]) dq.pollLast();
            dq.addLast(i);
            if (dq.peekFirst() <= i - k) dq.pollFirst();
            if (i >= k - 1) max[i - k + 1] = load[dq.peekFirst()];
        }
        System.out.println("максимум в каждом окне из " + k + ": " + Arrays.toString(max));
    }
}

Запустить

живой пример

package main

import "fmt"

func main() {
	load := []int{3, 1, 4, 1, 5, 9, 2, 6}
	k := 3
	maxes := make([]int, 0, len(load)-k+1)
	var dq []int // индексы, значения по ним убывают от головы к хвосту
	for i := range load {
		for len(dq) > 0 && load[dq[len(dq)-1]] <= load[i] {
			dq = dq[:len(dq)-1]
		}
		dq = append(dq, i)
		if dq[0] <= i-k {
			dq = dq[1:]
		}
		if i >= k-1 {
			maxes = append(maxes, load[dq[0]])
		}
	}
	fmt.Printf("максимум в каждом окне из %d: %v\n", k, maxes)
}

Запустить

живой пример

const load = [3, 1, 4, 1, 5, 9, 2, 6];
const k = 3;
const max = [];
const dq = [];   // индексы, значения по ним убывают от головы к хвосту
let head = 0;    // голова очереди индексом: shift стоил бы O(N)
for (let i = 0; i < load.length; i++) {
  while (dq.length > head && load[dq.at(-1)] <= load[i]) dq.pop();
  dq.push(i);
  if (dq[head] <= i - k) head++;
  if (i >= k - 1) max.push(load[dq[head]]);
}
console.log(`максимум в каждом окне из ${k}: [${max.join(", ")}]`);

Запустить

живой пример

from collections import deque

load = [3, 1, 4, 1, 5, 9, 2, 6]
k = 3
window_max = []
dq = deque()   # индексы, значения по ним убывают от головы к хвосту
for i, value in enumerate(load):
    while dq and load[dq[-1]] <= value:
        dq.pop()
    dq.append(i)
    if dq[0] <= i - k:
        dq.popleft()
    if i >= k - 1:
        window_max.append(load[dq[0]])
print(f"максимум в каждом окне из {k}: {window_max}")

Запустить

В очереди индексы с убывающими значениями: голова это максимум текущего окна, хвост чистят от тех, кого новый элемент превзошёл, голову от тех, кто выпал из окна. Так считают пиковую нагрузку за последние N минут по потоку метрик за один проход.

Задача о наибольшем прямоугольнике под гистограммой выглядит иначе, а решается тем же стеком. Для каждого столбца прямоугольник его высоты тянется влево и вправо до первого столбца ниже; значит, нужны ближайшие меньшие с обеих сторон, и это ровно монотонный стек. Когда столбец выталкивают из стека, его правая граница найдена (это текущий индекс), а левая это новый верх стека; площадь высота × (правая − левая − 1) сравнивают с лучшей. Один проход со стражем в конце, O(N).

Как узнать приём в задаче

В условии есть слова «ближайший больший», «следующий меньший», «через сколько шагов впервые».
Наивное решение — вложенный цикл, который бежит вперёд или назад до первого подходящего.
Нужен максимум или минимум в скользящем окне — это монотонная очередь.
Задача про прямоугольники под гистограммой или про воду между столбиками — тот же приём в другой одежде.

Как это сделано в стандартной библиотеке

Свой стек писать не нужно: он есть в стандартной библиотеке и в примерах выше уже использован. Понимать стоит другое — что за ним стоит.

ArrayDeque — обычный массив плюс два индекса, голова и хвост, с переходом через край обратно в начало массива; когда места перестаёт хватать, содержимое переезжает в массив побольше. Всё, что нужно приёму, стоит O(1) амортизированно: push кладёт элемент в голову, pop снимает оттуда же, peek смотрит на верхний, не снимая.

Тот же класс закрывает и монотонную очередь: стеку хватает трёх методов с одного конца, а очереди нужны оба — peekLast и pollLast с хвоста, pollFirst с головы. Переходя от стека к очереди, структуру менять не приходится, меняются вызовы.

Класс Stack из первых версий Java для этого не берут: внутри у него Vector, каждый метод синхронизирован — за блокировки платишь даже в одном потоке, где они не нужны, — а перебирается он снизу вверх, в порядке, обратном тому, в котором сам же отдаёт элементы. Разбор — в статье о стеках и очередях.

Грабля вылезает как раз в монотонном приёме. В стеке лежат индексы, то есть тип получается Deque<Integer> — объекты, и в строке revenue[waiting.peek()] каждый раз происходит распаковка обратно в число. На пустом стеке peek() возвращает null, и распаковка null даёт NullPointerException — в строке, где ни одного явного null не написано. Именно поэтому проверка !waiting.isEmpty() в условии while стоит первой: короткое замыкание && — единственное, что не даёт выполниться второй половине условия. Переставьте их местами, и код упадёт на первом же элементе. Если и упаковка, и null мешают, лекарство простое: стек индексов держат в собственном int[] длиной N с переменной вершины top; push это stack[++top] = i, pop это stack[top--], а isEmpty это top < 0. Больше N элементов в стеке не бывает, объектов нет вовсе, и это самый быстрый вариант приёма.

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

Срез — обычный массив с длиной и ёмкостью; когда места перестаёт хватать, append переезжает в массив побольше. Всё, что нужно приёму, стоит O(1) амортизированно: append кладёт элемент на вершину, s[:len(s)-1] снимает, s[len(s)-1] смотрит на верхний, не снимая.

Тот же срез закрывает и монотонную очередь: стеку хватает операций с одного конца, а очереди нужны оба — снятие с хвоста через s[:len(s)-1] и с головы через s[1:] или индекс головы. Переходя от стека к очереди, структуру менять не приходится, меняются операции. container/list здесь не нужен: он платит объектом-узлом и упаковкой в any за каждый индекс, а срез хранит int подряд. Разбор — в статье о стеках и очередях.

Грабля вылезает как раз в монотонном приёме. В стеке лежат индексы, и в строке revenue[waiting[len(waiting)-1]] на пустом срезе индекс -1 даёт панику index out of range — в строке, где ни одного явного -1 не написано. Именно поэтому проверка len(waiting) > 0 в условии for стоит первой: короткое замыкание && — единственное, что не даёт выполниться второй половине условия. Переставьте их местами, и код упадёт на первом же элементе. Утечки памяти у стека на срезе нет, пока он живёт внутри одного прохода; а для очереди с q[1:] помнят, что срез держит весь исходный массив, поэтому в долгоживущем окне берут индекс головы.

Свой стек писать не нужно: в JavaScript это обычный массив, и в примерах выше он уже использован. Понимать стоит другое — что за ним стоит.

Array в роли стека — плотный массив с запасом; когда места перестаёт хватать, движок переезжает в массив побольше. Всё, что нужно приёму, стоит O(1) амортизированно: push кладёт элемент на вершину, pop снимает, at(-1) смотрит на верхний, не снимая.

С монотонной очередью сложнее: снимать с хвоста можно тем же pop, а вот shift с головы сдвигает весь массив и стоит O(N). На окне из трёх элементов это незаметно, на очереди в сотни тысяч — квадратично. Поэтому в примере с максимумом окна голову очереди держит индекс head, который только растёт, а сам массив не трогают; для долгоживущих очередей берут пакет denque. Разбор — в статье о стеках и очередях.

Грабля вылезает как раз в монотонном приёме, и она тише, чем в других языках. На пустом массиве waiting.at(-1) возвращает undefined, revenue[undefined] тоже undefined, а сравнение с undefined даёт false — без исключения. Цикл просто останавливается, и код выглядит работающим, но проверка waiting.length > 0 в условии while всё равно должна стоять первой: полагаться на то, что сравнение с undefined случайно даст нужный ответ, нельзя, при >= вместо > или при NaN в данных логика поплывёт молча. Индексы в массиве — обычные числа без упаковки; для очень больших N стек индексов держат в Int32Array(N) с переменной вершины top: push это stack[++top] = i, pop это stack[top--], а «пусто» это top < 0.

Свой стек писать не нужно: в Python это обычный list, и в примерах выше он уже использован. Понимать стоит другое — что за ним стоит.

list в роли стека — массив ссылок с запасом; когда места перестаёт хватать, интерпретатор переезжает в массив побольше. Всё, что нужно приёму, стоит O(1) амортизированно: append кладёт элемент на вершину, pop() снимает, [-1] смотрит на верхний, не снимая.

Монотонной очереди list уже не хватает: снимать с хвоста можно тем же pop(), а pop(0) с головы сдвигает весь список и стоит O(N). Поэтому в примере с максимумом окна взят collections.deque: pop с хвоста, popleft с головы, [0] и [-1] по концам — всё O(1). Переходя от стека к очереди, меняют класс, а не логику. Разбор — в статье о стеках и очередях.

Грабля вылезает как раз в монотонном приёме. В стеке лежат индексы, и в строке revenue[waiting[-1]] на пустом списке waiting[-1] даёт IndexError — в строке, где ни одного явного индекса не написано. Именно поэтому проверка while waiting and ... стоит первой: короткое замыкание and — единственное, что не даёт выполниться второй половине условия. Переставьте их местами, и код упадёт на первом же элементе. Индексы в списке — объекты int, но маленькие целые интерпретатор кеширует, так что упаковки, как в Java, здесь почти нет; на очень больших N стек индексов держат в array('i') или массиве NumPy с переменной вершины top, чтобы не платить за объекты.

Коротко

Монотонный стек хранит элементы, ещё ожидающие ответа, в упорядоченном виде; новый элемент закрывает сразу всех, кого превзошёл.
Хранят индексы, а не значения: по индексу доступны и значение, и расстояние.
Время O(N) несмотря на вложенный цикл: каждый элемент кладётся и снимается не более одного раза.
Строгое > или нестрогое >= выбирается по формулировке; на данных с повторами ошибка проявляется сразу.
Родственный приём — монотонная очередь для максимума в скользящем окне: убирает с хвоста меньших, с головы выпавших из окна.
Страж в конце массива опустошает стек сам; для ближайшего меньшего переворачивают знак, и стек становится убывающим.
Монотонная очередь на деке даёт максимум окна за один проход; наибольший прямоугольник под гистограммой это ближайшие меньшие с двух сторон тем же стеком.

Берут ArrayDeque, а не Stack; проверка на пустоту стоит перед peek(), иначе распаковка null роняет код; стек индексов без упаковки держат в int[] с вершиной top.

Стек и монотонная очередь это срез; проверка len(s) > 0 стоит перед s[len(s)-1], иначе паника; для долгоживущей очереди индекс головы вместо q[1:].

Стек это массив с push, pop и at(-1); shift с головы O(N), голову очереди держат индексом; at(-1) на пустом даёт undefined, и цикл молча останавливается, проверка length первой.

Стек это list, монотонная очередь deque с popleft; проверка while waiting and ... стоит первой, иначе waiting[-1] даёт IndexError.

Что почитать дальше

Стеки и очереди — та самая структура, на которой держится приём.
Два указателя и скользящее окно — окно, для которого нужна монотонная очередь.
Математика для O-нотации — почему сумма ограниченных шагов даёт O(N).
Как выбрать структуру данных — когда стек, а когда дерево или хеш-таблица.