Структуры данных

Monotonic Stack: Паттерн 'следующий больший'

Цели урока

  • Понять паттерн 'следующий больший/меньший'
  • Реализовать monotonic stack за O(n)
  • Освоить вариации: next/prev, greater/smaller
  • Решить Largest Rectangle in Histogram

Предварительные знания

  • Стеки
  • Стеки

LeetCode задача 'Daily Temperatures': для каждого дня найти через сколько дней потеплеет. Наивно O(n²), но один простой трюк со стеком - и O(n). Этот паттерн решает десятки задач!

  • Биржевые данные - Stock Span Problem
  • Прогноз погоды - Daily Temperatures
  • Компьютерная графика - Skyline Problem
  • Анализ гистограмм - Largest Rectangle

От фольклора олимпиад до стандарта собеседований

Монотонный стек вырос из сообщества соревновательного программирования, а не из одной публикации. Его характерные задачи сформировались в 1980-х и 1990-х годах: Largest Rectangle in Histogram стала стандартным упражнением о площади под силуэтом столбцов, а Next Greater Element и Stock Span Problem превратили ту же идею в переиспользуемый шаблон сканирования. Техника долго оставалась устной традицией, которую передавали между участниками олимпиад, пока в 2010-х годах ростом сайтов подготовки к собеседованиям эти задачи не собрали вместе. Там монотонный стек был распознан как одна общая техника: храним стек, значения которого остаются отсортированными, и выталкиваем элементы в тот момент, когда приходящий элемент делает их ненужными. Сегодня он встречается в задачах от Daily Temperatures до Trapping Rain Water, и все они являются вариациями поиска ближайшего большего или меньшего элемента за линейное время.

Проблема: Next Greater Element

**Задача:** для каждого элемента найти следующий больший справа.

**Наивное решение:** для каждого элемента ищем вправо → O(n²). Но можно за O(n)!

Next Greater Element для arr=[3,1,2] это:

Идея: Монотонно убывающий стек

**Инвариант:** храним стек индексов элементов в порядке убывания значений.

**Почему O(n)?** Каждый элемент push один раз и pop максимум один раз. Итого ≤ 2n операций.

Monotonic decreasing stack поддерживает:

Реализация Next Greater Element

**Шаблон:** итерируем → пока текущий 'лучше' вершины стека → pop и записываем ответ → push текущий.

Когда элемент попадает в result?

Вариации: Меньший, слева, циклический

ЗадачаСтекНаправление
Next GreaterDecreasingСлева направо
Next SmallerIncreasingСлева направо
Prev GreaterDecreasingСправа налево
Prev SmallerIncreasingСправа налево

Для 'Previous Smaller Element' нужен:

Классические задачи

**Largest Rectangle in Histogram** - классика LeetCode, решается через monotonic stack за O(n).

  • **Daily Temperatures** - через сколько дней будет теплее?
  • **Stock Span** - сколько дней подряд цена была ≤ текущей
  • **Trapping Rain Water** - сколько воды между столбцами
  • **Largest Rectangle in Histogram** - максимальная площадь

Monotonic Stack подходит для задач типа:

Monotonic Stack

  • Стек с элементами в монотонном порядке
  • Decreasing stack → Next Greater Element
  • Increasing stack → Next Smaller Element
  • Итерация справа налево → Previous элемент
  • O(n) время: каждый элемент push/pop один раз

Паттерны на массивах

Monotonic Stack - один из базовых паттернов. Другие: Two Pointers, Sliding Window, Prefix Sum. Комбинируя их, можно решить большинство задач на массивы.

  • Стеки — Базовая структура для Monotonic Stack

Связанные уроки

  • ds-03-stacks — Строит паттерн прямо поверх обычного стека
  • alg-26-two-pointers — Обе дают O(n), не возвращаясь к уже пройденным элементам
  • alg-27-sliding-window — Скользящее окно так же амортизирует работу до O(n)
  • alg-03-amortized — Каждый элемент кладётся и снимается раз - амортизированная оценка
  • ds-14-heaps-intro — Кучи - альтернатива для запросов текущего минимума и максимума
  • alg-36-prefix-sum
Monotonic Stack: Паттерн 'следующий больший'

0

1

Войти