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

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

Что такое монотонный стек и как он работает

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

Представьте, что вы собираете команду для рейда. Вы выстраиваете союзников по силе. Когда появляется более сильный, вы отправляете слабых на скамейку — они больше не пригодятся в текущем бою. Стек хранит только тех, кто может понадобиться позже. Всё остальное решается на месте.

Задача 1: Next Greater Element I

Даны два массива nums1 и nums2, где nums1 — подмножество nums2. Для каждого элемента из nums1 найдите следующий больший элемент справа в nums2. Если его нет, выведите -1.

Перебор (O(n²)) — подход «зубочистки»

def next_greater_brute(nums1, nums2):
    res = []
    for x in nums1:
        i = nums2.index(x)  # O(n) поиск
        nxt = -1
        for y in nums2[i+1:]:  # сканируем справа
            if y > x:
                nxt = y
                break
        res.append(nxt)
    return res

Монотонный стек (O(n)) — настоящее решение

def next_greater(nums1, nums2):
    # словарь: число -> следующий больший
    nxt = {}
    stack = []  # будет хранить убывающий стек

    for num in nums2:
        # пока стек не пуст и текущее число больше вершины
        while stack and num > stack[-1]:
            prev = stack.pop()  # для prev нашли следующий больший
            nxt[prev] = num
        stack.append(num)

    # оставшиеся в стеке не имеют большего элемента
    while stack:
        nxt[stack.pop()] = -1

    # собираем ответ для nums1
    return [nxt[x] for x in nums1]

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

Типичная ошибка: забыть очистить стек в конце. Оставшиеся элементы действительно не имеют большего, поэтому им нужно присвоить -1, иначе словарь будет неполным.

Задача 2: Largest Rectangle in Histogram

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

Перебор всех пар границ даёт O(n²) — некрасиво. Решение с монотонным стеком (возрастающий стек):

def largest_rectangle(heights):
    stack = []  # хранит индексы, высоты возрастают
    max_area = 0

    # добавляем страж 0, чтобы очистить стек в конце
    for i, h in enumerate(heights + [0]):
        while stack and h < heights[stack[-1]]:
            height = heights[stack.pop()]
            # ширина: текущий индекс минус индекс новой вершины минус 1
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)

    return max_area

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

Типичная ошибка: использование <= вместо < при решении о pop. С равными высотами вы вытолкнете преждевременно и потеряете более широкие прямоугольники. Придерживайтесь строгого < для логики «первый меньший справа».

Где ещё применить монотонный стек

С этим инструментом вы можете решить целый класс задач на собеседованиях за линейное время:

• Daily Temperatures (следующий более тёплый день)
• Sum of Subarray Minimums (классическая задача с LeetCode уровня hard)
• Trapping Rain Water (рассматривается как два монотонных прохода)
• Online Stock Span

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

Практический вывод: ваш следующий шаг

Выберите одну из задач выше (или найдите новую, которая «пахнет» next greater/lesser) и реализуйте её с помощью монотонного стека. Попробуйте объяснить другу, почему каждый push/pop соответствует реальному решению о структуре массива. Когда получится — оставьте комментарий с решением или ссылку на репозиторий. Удачи в стеке! 🚀