Monotonic stack — это стек, в котором мы специально поддерживаем
монотонный порядок элементов: либо возрастающий, либо убывающий.
То есть это не просто стек «последний вошёл — первый вышел», а стек с правилом:
пока новый элемент ломает порядок —
выкидываем элементы сверху стека
потом кладём новый элемент
Главная идея:
стек хранит только тех кандидатов, которые ещё могут пригодиться
А те, кто уже точно проиграл новому элементу, удаляются.
Есть массив:
[2, 1, 5, 3, 4]
Допустим, мы хотим найти для каждого числа следующее большее справа.
То есть:
2 -> 5
1 -> 5
5 -> нет
3 -> 4
4 -> нет
Для этого удобно использовать monotonic decreasing stack — стек, где
элементы ждут следующее большее число.
Идём слева направо.
Видим 2:
stack = [2]
Пока ничего не знаем.
Видим 1.
1 не больше 2, значит не может закрыть 2.
stack = [2, 1]
Видим 5.
5 больше 1, значит для 1 найдено следующее большее:
1 -> 5
stack = [2]
5 больше 2, значит для 2 тоже найдено следующее большее:
2 -> 5
stack = []
Кладём 5:
stack = [5]
Видим 3.
3 не больше 5.
stack = [5, 3]
Видим 4.
4 больше 3:
3 -> 4
stack = [5]
Но 4 не больше 5, значит 5 остаётся ждать.
stack = [5, 4]
В конце те, кто остался в стеке, не нашли большего справа:
5 -> нет
4 -> нет
Базовый шаблон
Для задач типа next greater element:
def next_greater(nums):
result = [-1] * len(nums)
stack = [] # здесь будут индексы
for i, x in enumerate(nums):
while stack and nums[stack[-1]] < x:
j = stack.pop()
result[j] = x
stack.append(i)
return result
Для:
nums = [2, 1, 5, 3, 4]
результат:
[5, 5, -1, 4, -1]
Почему в стеке обычно хранят индексы
Можно хранить значения:
stack = [2, 1]
Но чаще хранят индексы:
stack = [0, 1]
Потому что индекс даёт доступ сразу к двум вещам:
nums[index] # само значение
index # позиция элемента
Это важно, например, в задаче Daily Temperatures, где нужно не просто найти
следующую большую температуру, а посчитать расстояние до неё.
Пример: Daily Temperatures
Задача:
temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
Для каждого дня найти, через сколько дней будет теплее.
Ответ:
[1, 1, 4, 2, 1, 1, 0, 0]
Код:
def daily_temperatures(temperatures):
result = [0] * len(temperatures)
stack = [] # индексы дней, для которых ещё не нашли более тёплый день
for i, temp in enumerate(temperatures):
while stack and temperatures[stack[-1]] < temp:
prev_i = stack.pop()
result[prev_i] = i - prev_i
stack.append(i)
return result
Здесь стек хранит дни, температура которых ещё ждёт более тёплого дня.
Почему это O(n), хотя внутри есть while
На первый взгляд кажется:
for + while = O(n^2)
Но нет.
Каждый элемент:
1 раз добавляется в стек
1 раз удаляется из стека
То есть элемент не может бесконечно pop-аться. Его положили, потом однажды
выкинули — всё.
Поэтому общее количество операций push и pop за весь алгоритм:
O(n)
Это называется amortized O(n).
Локально один шаг может выкинуть много элементов, но суммарно за весь проход
каждый элемент выкидывается максимум один раз.
Increasing stack и decreasing stack
Есть две основные формы.
Monotonic increasing stack
Стек поддерживает возрастающий порядок.
Например:
[1, 3, 5, 8]
Когда приходит новый элемент меньше верхнего, мы удаляем верхние элементы.
Шаблон:
while stack and stack[-1] > x:
stack.pop()
stack.append(x)
Такой стек часто помогает искать:
previous smaller
next smaller
минимальные элементы
лексикографически минимальную последовательность
Monotonic decreasing stack
Стек поддерживает убывающий порядок.
Например:
[8, 5, 3, 1]
Когда приходит новый элемент больше верхнего, мы удаляем верхние элементы.
Шаблон:
while stack and stack[-1] < x:
stack.pop()
stack.append(x)
Такой стек часто помогает искать:
previous greater
next greater
следующий больший элемент
более тёплый день
Главное различение
seen set:
элемент -> уже был или нет
frequency map:
элемент -> сколько раз встретился
grouping:
ключ -> список элементов
monotonic stack:
держим кандидатов в порядке,
а тех, кто больше не может быть ответом, выкидываем
То есть это не структура данных сама по себе, а паттерн управления стеком.
Интуитивная формула
Monotonic stack отвечает на вопрос:
какие элементы ещё ждут своего закрывающего элемента справа?
Например:
число ждёт следующее большее число
температура ждёт более тёплый день
здание ждёт более высокое здание
цена ждёт падение/рост
Когда появляется новый элемент, он может закрыть несколько старых элементов
сразу.
Где часто встречается
Классические задачи:
Next Greater Element
Next Smaller Element
Daily Temperatures
Largest Rectangle in Histogram
Trapping Rain Water
Remove K Digits
Stock Span Problem
Sum of Subarray Minimums
Особенно характерный признак задачи:
найти ближайший следующий больший/меньший элемент слева или справа
Если видишь формулировку:
next greater
next smaller
previous greater
previous smaller
nearest greater
nearest smaller
почти всегда где-то рядом лежит monotonic stack.
