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

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

Помните, как впервые увидели задачу Daily Temperatures на LeetCode и пытались решить её двумя вложенными циклами? Простое решение — O(n²) — валилось на больших тестах. А что, если я скажу, что есть способ пройти массив один раз и получить ответы для всех элементов? Монотонный стек — это именно то, что нужно. Он превращает квадратичную сложность в линейную и открывает дверь к целому классу задач.

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

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

Разбор на примере Daily Temperatures

Вот как выглядит наивное решение:

def daily_temperatures_bruteforce(temps):
    n = len(temps)
    answer = [0] * n
    for i in range(n):
        for j in range(i+1, n):
            if temps[j] > temps[i]:
                answer[i] = j - i
                break
    return answer

А вот с монотонным стеком:

def daily_temperatures(temps):
    n = len(temps)
    answer = [0] * n
    stack = []  # храним индексы, значения убывают
    for i, t in enumerate(temps):
        # пока текущая температура больше верхушки стека
        while stack and temps[stack[-1]] < t:
            prev = stack.pop()
            answer[prev] = i - prev
        stack.append(i)
    # оставшиеся индексы — нет более тёплого дня
    return answer

Каждый индекс добавляется и удаляется из стека максимум один раз. Время — O(n), память — O(n).

Ещё один классический пример: Largest Rectangle in Histogram

Здесь нужно найти предыдущий меньший и следующий меньший для каждого столбца. Принцип тот же:

def largest_rectangle_area(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 - индекс предыдущего в стеке - 1
            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 или другое значение по умолчанию.

Почему это важно

Освоив монотонный стек, вы с лёгкостью решите десятки задач с собеседований: Daily Temperatures, Next Greater Element, Largest Rectangle in Histogram, Sum of Subarray Minimums, Trapping Rain Water и другие. Вы перестанете писать двойные циклы и начнёте видеть паттерн: «Нужен ближайший элемент, который больше (или меньше) текущего при монотонном условии». Это как получить новое заклинание — сразу становится легче.

Ваша очередь

Попробуйте решить задачу Sum of Subarray Minimums (LeetCode 907) с помощью монотонного стека. Подумайте, почему вклад каждого элемента равен left * right * value, где left — расстояние до предыдущего строго меньшего, а right — до следующего меньшего или равного. Пишите свои решения в комментариях — посмотрим, кто справится элегантнее!