Монотонный стек: секрет O(n) для задач с массивами

Зачем это читать?

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

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

Монотонный стек — это обычный стек, элементы в котором хранятся в строго монотонном порядке (возрастающем или убывающем) по мере прохода по массиву. Каждый элемент помещается в стек один раз и извлекается не более одного раза. Итоговая сложность — O(n), хотя внутри может быть много операций извлечения.

Рассмотрим классическую задачу Next Greater Element: для каждого индекса i найти первый элемент справа, который больше nums[i]. Если идти слева направо и поддерживать убывающий стек (вершина — наименьший), то:

• Когда встречаем новое значение x, все элементы стека, которые меньше x, наконец-то находят свой следующий больший — это x!
• Извлекаем эти элементы, записываем для них ответ, и продолжаем, пока стек не опустеет или его вершина не станет ≥ x.
• Затем помещаем x в стек, сохраняя убывающий порядок.

Каждый элемент может быть извлечён только тогда, когда встретит большего соседа — никакой лишней работы. Стек никогда не содержит более O(n) элементов, и каждый элемент испытывает не более одного помещения и одного извлечения. В этом суть: стек фиксирует причинно-следственную связь — как только элемент заблокирован большим, его судьба решена навсегда.

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

Пример кода: Next Greater Element

Наивный подход O(n²)

def next_greater_brute(nums):
    res = [-1] * len(nums)
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if nums[j] > nums[i]:
                res[i] = nums[j]
                break
    return res

Два вложенных цикла — если массив убывает, для каждого индекса сканируем весь хвост. Ужасно.

Монотонный стек O(n)

def next_greater_element(nums):
    res = [-1] * len(nums)
    stack = []  # храним индексы, nums[stack] убывает
    for i in range(len(nums)):
        # Извлекаем все индексы, для которых nums[i] — следующий больший
        while stack and nums[i] > nums[stack[-1]]:
            idx = stack.pop()
            res[idx] = nums[i]
        stack.append(i)
    return res

Почему это работает: стек хранит индексы, у которых ещё нет следующего большего, и они расположены в порядке убывания значений. Когда новое значение нарушает этот порядок, оно становится первым большим справа для всех меньших индексов — именно то, что нужно. Каждый индекс помещается один раз и извлекается не более одного раза → O(n) времени, O(n) памяти.

Ещё один хит: Largest Rectangle in Histogram

Задача «наибольший прямоугольник в гистограмме» — любимица интервьюеров. Наивное решение (проверка всех пар границ) — O(n²). Монотонный стек (на этот раз возрастающий) — O(n).

def largest_rectangle_area(heights):
    stack = []  # индексы с возрастающими высотами
    max_area = 0
    extended = heights + [0]  # дозорный, чтобы опустошить стек
    for i in range(len(extended)):
        while stack and extended[i] < extended[stack[-1]]:
            height = extended[stack.pop()]
            # ширина: если стек пуст, прямоугольник тянется от начала
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)
    return max_area

Распространённые ловушки:

• Забыть дозорный ноль в конце — тогда часть столбцов останется необработанной.
• Путать индексы и значения: хранить нужно индексы, чтобы легко вычислять ширину.
• Некорректная обработка равных высот: используйте строгое сравнение (<), чтобы не терять информацию на плато.

Почему это меняет всё?

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

• Stock Span — дневной размах как расстояние до предыдущей более высокой цены.
• Maximum Width Ramp — найти max(j-i), где A[i] ≤ A[j]; используем убывающий стек кандидатов.
• Trapping Rain Water — вычисление левой и правой границ с помощью двух монотонных проходов.

Все эти задачи решаются за O(n) времени и O(n) памяти. Код настолько короток, что его можно написать на доске за минуту, а объяснение простое: «Я поддерживаю стек в монотонном порядке; когда порядок нарушается, я нахожу ответ для всех извлечённых элементов».

Практический вывод

Попробуйте сами: дан массив nums, найдите максимальное значение nums[j] - nums[i] при i < j и nums[i] ≤ nums[j] (максимальная прибыль от одной сделки, где можно продать только после покупки). Адаптируйте монотонный стек для решения за O(n). Напишите решение в комментариях — давайте продолжим приключение! 🚀