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

Зачем вам монотонный стек?

Вы когда-нибудь застревали на задаче «Next Greater Element»? Массив выглядит безобидно, но перебор с вложенными циклами даёт O(n²) и ощущение, что вы долбите гвоздь мокрым одеялом. Знакомая боль? Тогда добро пожаловать: монотонный стек — это элегантный способ смотреть в будущее, не оглядываясь назад каждый раз. Освоив его, вы превратите ночные кошмары из собеседований в простые линейные проходы.

Суть техники: инвариант монотонности

Монотонный стек — это обычный стек, элементы которого хранятся в строго возрастающем или убывающем порядке. Зачем это нужно? Рассмотрим задачу поиска следующего большего элемента: для каждого индекса i нужно найти первый справа элемент, больший arr[i].

Если идти слева направо и хранить в стеке индексы, для которых ещё не найден ответ, стек естественным образом будет убывающим по значениям. Почему? Представьте, что стек содержит индексы [i₁, i₂, …, i_k] с arr[i₁] > arr[i₂] > … > arr[i_k]. Когда мы встречаем новое значение arr[j], любой элемент стека, который меньше arr[j], только что нашёл свой следующий больший элемент — это arr[j]. Мы выталкиваем эти индексы, записываем ответ и останавливаемся, когда стек пуст или верхушка не меньше. Затем добавляем j в стек.

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

Практика: разбор двух классических задач

1. Next Greater Element (NGE)

Начнём с самой известной задачи. Сначала покажем, как выглядит «наивный» перебор, а затем — как монотонный стек превращает его в линейный алгоритм.

Наивное решение (борьба):

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

Здесь O(n²) времени и O(1) дополнительной памяти (не считая вывода).

Решение с монотонным стеком (победа):

def next_greater(arr):
    n = len(arr)
    res = [-1] * n
    stack = []  # храним индексы, значения убывают
    for i, value in enumerate(arr):
        # Разрешаем индексы, ожидающие больший элемент
        while stack and arr[stack[-1]] < value:
            idx = stack.pop()
            res[idx] = value
        stack.append(i)
    return res

Почему это работает?

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

Частая ошибка: забыть про строгость сравнения. Если нужно найти строго больший элемент, используйте <. Если поставить <=, то равные значения будут ошибочно считаться ответами, что ломает решение на входе типа [5, 5, 5].

2. Наибольший прямоугольник в гистограмме

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

Наивный подход: для каждого столбца расширяемся влево и вправо, пока не встретим меньший → O(n²).

Решение через монотонный стек:

def largest_rectangle(heights):
    stack = []  # индексы с возрастающими высотами
    max_area = 0
    # Добавляем фиктивную высоту 0, чтобы вытолкнуть всё в конце
    for i, h in enumerate(heights + [0]):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            # Ширина: i, если стек пуст, иначе расстояние до предыдущего меньшего
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)
    return max_area

Почему это работает?

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

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

Почему это важно за пределами собеседований

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

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

В следующий раз, когда увидите массив и почувствуете знакомую тревогу, спросите себя: «Могу ли я поддерживать монотонное свойство во время прохода?» Если да — вы нашли свой O(n) лайфхак.

Практическое задание

Закрепите навык на задаче Daily Temperatures (LeetCode 739). Дан массив T с ежедневными температурами, верните массив, где каждый элемент показывает, сколько дней нужно ждать более тёплой погоды. Если такого дня нет, ставьте 0.

Попробуйте решить её с помощью монотонно убывающего стека, а затем сравните с наивным перебором. Напишите свой вариант в комментариях — посмотрим, у кого получится самый элегантный трюк!

Удачного кодинга, и пусть ваши стеки всегда остаются монотонными! 🚀