Монотонный стек: как узнать его в задаче и написать за 10 минут

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

Что такое монотонный стек?

Это стек с одним дополнительным правилом. Новый элемент кладут не сразу. Сначала со стека снимают всё, что ломает порядок.

Пример для убывающего стека. Идём по массиву [5, 3, 4, 8].

• Кладём 5. Стек: [5].
• Кладём 3. Оно меньше 5, порядок цел. Стек: [5, 3].
• Приходит 4. Снимаем 3, оно меньше 4. Кладём 4. Стек: [5, 4].
• Приходит 8. Снимаем 4 и 5. Стек: [8].

Каждое снятие это ответ. Четвёрка сняла тройку. Значит, ближайшее большее справа от 3 это 4.

Как узнать монотонный стек в условии задачи?

Слова в условии выдают паттерн раньше, чем ты начнёшь думать. Вот они.

• «Ближайший больший элемент справа» или «слева».
• «Следующий тёплый день», «через сколько дней».
• «Наибольший прямоугольник в гистограмме».
• «Сколько элементов подряд не больше текущего».
• Любое «для каждого элемента найди первый, который…».

Общий признак один. Для каждого элемента нужен один сосед, а лобовое решение даёт O(n²). Монотонный стек сводит это к O(n).

Подробнее о сигналах и соседях паттерна на странице монотонного стека. Там же шаблоны на шести языках.

Как написать монотонный стек на Python?

Классическая задача: для каждого элемента найти ближайший больший справа. Нет такого, ставим -1.

def next_greater(nums):
    answer = [-1] * len(nums)
    stack = []  # индексы, значения по убыванию

    for i, value in enumerate(nums):
        while stack and nums[stack[-1]] < value:
            j = stack.pop()
            answer[j] = value
        stack.append(i)

    return answer

Три детали, на которых держится код.

• В стеке лежат индексы, а не значения. Так ты знаешь, кому записать ответ.
• Цикл while снимает всё, что меньше нового элемента.
• Каждый индекс кладут один раз и снимают один раз. Отсюда O(n).

Нужен ближайший меньший? Поменяй знак сравнения. Нужен сосед слева? Ответ записывай в момент, когда кладёшь элемент.

Чем монотонный стек отличается от монотонной очереди?

Их путают чаще всего. Разница в том, откуда уходят элементы.

Признак	Монотонный стек	Монотонная очередь
Откуда снимают	Только с вершины	С обоих концов
Что ищем	Ближайшего соседа	Максимум или минимум в окне
Слова в условии	«ближайший», «следующий»	«окно размера k», «за последние k»
Типичная задача	Next Greater Element	Sliding Window Maximum

Если в условии есть окно фиксированной ширины, это монотонная очередь. Если сосед, это стек.

Какие задачи решает монотонный стек?

Пять задач, которые встречаются на собеседованиях чаще других.

• Next Greater Element. Базовая, её код выше.
• Daily Temperatures. То же самое, но ответ это расстояние в днях.
• Stock Span. Сколько дней подряд цена не выше сегодняшней.
• Largest Rectangle in Histogram. Для каждого столбца ищем меньших соседей с двух сторон.
• Trapping Rain Water. Стек хранит стенки, вода считается при снятии.

Первые три это одна и та же задача в разной обёртке. Решил одну, решил все.

Как разобрать задачу Daily Temperatures?

Условие. Дан массив температур по дням. Для каждого дня скажи, через сколько дней станет теплее. Если теплее не станет, ответ 0.

Сигнал виден сразу. «Через сколько дней» это расстояние до ближайшего большего справа.

Возьмём [73, 74, 75, 71, 69, 72]. Идём слева направо, в стеке индексы.

• День 0, 73 градуса. Стек пуст, кладём 0.
• День 1, 74. Снимаем день 0: ответ для него 1 - 0 = 1. Кладём 1.
• День 2, 75. Снимаем день 1, ответ 1. Кладём 2.
• Дни 3 и 4, 71 и 69. Оба холоднее, просто кладём.
• День 5, 72. Снимаем день 4, ответ 1. Снимаем день 3, ответ 2. Кладём 5.

В стеке остались дни 2 и 5. Теплее для них не будет, ответ 0.

Итог: [1, 1, 0, 2, 1, 0]. Двойка у дня 3 потому, что его снял день 5.

Такую проверку стоит делать вслух и на собеседовании. Ошибку в индексе видно только на трассировке.

Как объяснить монотонный стек на собеседовании?

Интервьюер ждёт три фразы, и в таком порядке.

• «Для каждого элемента нужен ближайший больший справа. В лоб это O(n²).»
• «Держу стек индексов с убывающими значениями. Новый элемент снимает всех, кто меньше.»
• «Каждый индекс входит и выходит один раз, поэтому O(n).»

Потом код. Потом трассировка на маленьком примере. Сложность в конце ещё раз, по памяти.

Какие ошибки чаще всего?

Ошибки на монотонном стеке однотипные. Проверь свой код по списку.

• Хранить значения вместо индексов. Ответ некуда записать.
• Перепутать строгое и нестрогое сравнение. Равные элементы ломают ответ.
• Забыть, что после цикла в стеке что-то осталось. У этих элементов соседа нет.
• Идти не с той стороны. Соседа слева ищут при вставке, справа при снятии.

Как тренировать монотонный стек?

Сначала научись узнавать его по условию. Это отдельный навык, и о нём есть статья про паттерны.

Потом напиши next_greater по памяти три раза с перерывом в день. Потом Daily Temperatures без подсказок.

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

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

Монотонный стек хранит индексы или значения?

Индексы. По индексу можно достать значение, а по значению индекс нет.

Какая сложность у монотонного стека?

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

Когда стек возрастающий, а когда убывающий?

Ищешь большего соседа, держи стек убывающим. Ищешь меньшего, держи возрастающим.

Можно ли обойтись без стека?

Можно, за O(n²) двумя циклами. На собеседовании это засчитают как неоптимальное решение.