2. Монотонный стек

«Когда в потоке данных сохраняется строгий порядок, каждый новый элемент мгновенно находит свое место, решительно сбрасывая все, что слабее него».
— Брайан Керниган

💡 Связанные темы:

• 1. Теория. Стек — базовые принципы и реализация на срезах
• 5. Daily Temperatures — классическая задача на расстояние до следующего теплого дня
• 6. Next Greater Element I — комбинация монотонного стека с хеш-таблицей
• 7. Largest Rectangle in Histogram — «финальный босс»: поиск левых и правых границ за $O(N)$
• 2. Асимптотическая сложность. Big O, Big Theta, Big Omega — амортизационный анализ сложности

Введение: Линия горизонта в массиве

На технических интервью уровня Middle+ и Senior редко просят просто «написать стек». Вместо этого предлагают задачу, которая в лоб решается квадратичным перебором за $O(N^2)$, но интервьюер ждет элегантного линейного решения за $O(N)$.
В девяти случаях из десяти ключом к победе служит Монотонный стек (Monotonic Stack).

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

Бытовая метафора: шеренга людей

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

🎯 Вопросы для уточнения условий (Interview Warm-up)

1. Что искать:
   «Мы ищем следующий больший элемент (Next Greater) или следующий меньший (Next Smaller)? Справа или слева?»
   • Ищем больший справа $\implies$ монотонно убывающий стек;
   • Ищем меньший справа $\implies$ монотонно возрастающий стек.
2. Что возвращать:
   «Нужно вернуть само значение элемента, его индекс или расстояние (дельта индексов j - i)?»
   (В стеке всегда сохраняем индексы, а не значения! По индексу мы мгновенно восстановим и значение nums[idx], и расстояние i - idx).
3. Строгость сравнения:
   «Строго больше (>) или больше либо равно (>=)?»

Архитектура алгоритма: Next Greater Element

Пусть дан массив: nums = [2, 1, 2, 4, 3].
Требуется для каждого числа найти ближайшее большее число справа. Если такого нет — записать -1.

flowchart TD
    classDef entry   fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
    classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef accent  fill:#1e1b4b,stroke:#818cf8,stroke-width:1px,color:#f8fafc
    classDef success fill:#064e3b,stroke:#34d399,stroke-width:2px,color:#f8fafc
    classDef warning fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc

    A["nums = [2, 1, 2, 4, 3]"]:::entry --> B["Шаг i=0: nums[0]=2, стек: [0]"]:::process
    B --> C["Шаг i=1: nums[1]=1 (1 < 2), стек: [0, 1]"]:::process
    C --> D["Шаг i=2: nums[2]=2 (2 > 1) -> Pop(1), res[1]=2! Стек: [0, 2]"]:::accent
    D --> E["Шаг i=3: nums[3]=4 (4 > 2) -> Pop(2), res[2]=4; Pop(0), res[0]=4!<br/>Стек: [3]"]:::warning
    E --> F["Шаг i=4: nums[4]=3 (3 < 4), стек: [3, 4]"]:::process
    F --> G["Итог res: [4, 2, 4, -1, -1]"]:::success
  

🛠️ Идиоматичная реализация на Go

package monotonic

// NextGreaterElements находит следующий больший элемент справа за O(N).
func NextGreaterElements(nums []int) []int {
    n := len(nums)
    if n == 0 {
        return nil
    }

    // 1. Инициализируем массив ответов значениями по умолчанию -1
    res := make([]int, n)
    for i := range res {
        res[i] = -1
    }

    // 2. Стек хранит ИНДЕКСЫ.
    // Преаллокация capacity = n защищает от лишних реаллокаций среза.
    stack := make([]int, 0, n)

    for i := 0; i < n; i++ {
        // Пока стек не пуст И текущий элемент превышает элемент на вершине стека
        for len(stack) > 0 && nums[i] > nums[stack[len(stack)-1]] {
            topIdx := stack[len(stack)-1]
            stack = stack[:len(stack)-1] // Pop за O(1)

            // Текущий элемент nums[i] является следующим большим для nums[topIdx]
            res[topIdx] = nums[i]
        }

        // Кладем текущий индекс на вершину стека
        stack = append(stack, i)
    }

    return res
}

📊 Доказательство сложности: почему это $O(N)$, а не $O(N^2)$?

На первый взгляд вложенный цикл for len(stack) > 0 пугает кандидатов, заставляя предполагать $O(N^2)$.
Это классическое заблуждение. Применим амортизационный анализ:

1. Каждый индекс $i \in [0, n-1]$ попадает в стек (Push) ровно 1 раз во внешнем цикле;
2. Каждый индекс извлекается из стека (Pop) во внутреннем цикле не более 1 раза за всю жизнь программы;
3. Общее число операций со стеком:
   $$\text{Total Ops} \le N_{\text{push}} + N_{\text{pop}} \le 2N$$
4. Итоговая временная сложность: строго $O(N)$.

⚙️ Mechanical Sympathy: Почему монотонный стек молниеносен на CPU

1. Непрерывный underlying array: Срез stack := make([]int, 0, n) никогда не реаллоцируется, оставаясь в границах одного непрерывного блока оперативной памяти.
2. Zero GC Overheads: Стек хранит примитивные целые числа int. Сборщик мусора Go полностью игнорирует этот срез при обходе графа объектов.
3. L1 Кэш: Чтение stack[len(stack)-1] всегда попадает в самую горячую кэш-линию L1 процессора.

🛑 Подводные камни и частые ошибки

🗺️ Навигация