Алгоритмы с нуля
Монотонный стек
В прошлом уроке ты выучил очереди и деки. Сегодня ты выучишь мощный вариант стека: монотонный стек. Это стек, что держит специальное свойство: элементы внутри держатся в отсортированном порядке (либо возрастающем, либо убывающем). Когда ты хочешь добавить новый элемент, ты сначала удаляешь из стека любые элементы, что нарушают этот порядок. Ключевой insight: это нарушает классическое правило “последний добавленный — первый удалённый”, но каждый элемент всё ещё добавляется и удаляется не более одного раза, давая O(n) итого. Каноническая задача — найти следующий больший элемент (NGE) — для каждого элемента в массиве, найти следующий элемент справа что больше. Наивное решение O(n²), но монотонный стек решает за O(n).
После этого урока ты можешь объяснить что такое монотонный стек и как push-with-pop инвариант держит порядок, реализовать алгоритм монотонного стека чтобы найти следующий больший элемент для каждого элемента за O(n) время, пройти через конкретный пример пошагово, понять почему каждый элемент добавляется и удаляется не более одного раза и как это гарантирует O(n) итого время, и узнать другие задачи (следующий меньший, предыдущий больший) что подходят под паттерн монотонного стека.
Что такое монотонный стек?
Монотонный стек это вариант обычного стека что держит строгий порядок среди своих элементов. Вместо того чтобы позволить любому элементу быть добавленным, ты применяешь правило: элементы должны быть в возрастающем порядке (или убывающем порядке, зависит от твоего выбора). Когда новый элемент прибывает:
- Пока стек не пуст и вершина нарушает порядок, удали вершину.
- Добавь новый элемент.
Результат: после каждого добавления, содержимое стека формирует отсортированную последовательность.
Возрастающий vs. убывающий:
- Монотонный возрастающий: стек = [1, 3, 5, 7]. Когда ты добавляешь 2, удали 7, 5, 3 сначала. Потом добавь 2 → [1, 2].
- Монотонный убывающий: стек = [7, 5, 3, 1]. Когда ты добавляешь 6, удали 5, 3, 1 сначала. Потом добавь 6 → [7, 6].
Задача следующий-больший-элемент:
Дан массив, для каждого элемента, найди следующий элемент справа что больше. Если такого элемента нет, верни -1.
Пример: arr = [2, 1, 2, 4, 3]
- Элемент 2 (индекс 0): следующий больший это 4. Ответ: 4.
- Элемент 1 (индекс 1): следующий больший это 2. Ответ: 2.
- Элемент 2 (индекс 2): следующий больший это 4. Ответ: 4.
- Элемент 4 (индекс 3): нет больших элементов справа. Ответ: -1.
- Элемент 3 (индекс 4): нет больших элементов справа. Ответ: -1.
Наивный подход: O(n²)
Для каждого элемента, отсканируй все элементы справа чтобы найти следующий больший. Худший случай: n * n = O(n²).
function nextGreaterBrute(arr) {
const result = new Array(arr.length);
for (let i = 0; i < arr.length; i++) {
result[i] = -1; // По умолчанию: нет больших элементов
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] > arr[i]) {
result[i] = arr[j];
break;
}
}
}
return result;
}Это медленно. По мере того как ты читаешь больше элементов, стоимость вложенного цикла взрывается.
Подход монотонного стека: O(n)
Insight: обработай массив справа налево. Держи монотонный убывающий стек элементов, которые ты видел до сих пор. Для каждого нового элемента:
- Удали все элементы из стека что ≤ новому элементу (они не могут быть “следующий больший” ни для чего).
- Если стек не пуст, вершина это следующий больший элемент для текущего элемента.
- Добавь текущий элемент в стек.
Почему это работает? Стек действует как “список кандидатов”. К тому времени как ты посетишь элемент, стек уже содержит все возможные кандидаты справа, предварительно отфильтрованные и отсортированные.
Почему это O(n)? Каждый элемент добавляется один раз и удаляется не более одного раза. Так что итого операций = O(2n) = O(n).
Решение монотонного стека для следующий больший элемент:
function nextGreater(arr) {
const stack = []; // Стек индексов (не значений)
const result = new Array(arr.length).fill(-1);
// Обработай справа налево
for (let i = arr.length - 1; i >= 0; i--) {
// Удали элементы что <= текущему элементу
while (stack.length > 0 && arr[stack[stack.length - 1]] <= arr[i]) {
stack.pop();
}
// Если стек не пуст, вершина это следующий больший элемент
if (stack.length > 0) {
result[i] = arr[stack[stack.length - 1]];
}
// Добавь текущий индекс
stack.push(i);
}
return result;
}Почему мы храним индексы, не значения:
Мы добавляем индексы в стек, так что позже, когда нам нужно фактическое значение следующего большего элемента, мы можем индексировать в массив. Этот pattern часто встречается в задачах с монотонным стеком.
Попробуй в интерактивном runner:
Давай пройдём через алгоритм монотонного стека на массиве [2, 1, 2, 4, 3].
Мы обрабатываем справа налево (i = 4, 3, 2, 1, 0). На каждом шаге, мы удаляем индексы чьи значения ≤ текущему значению, потом добавляем текущий индекс.
1
for (let i = arr.length - 1; i >= 0; i--) {
2
while (stack.length > 0 && arr[stack[stack.length - 1]] <= arr[i]) {
3
stack.pop();
4
}
5
if (stack.length > 0) {
6
result[i] = arr[stack[stack.length - 1]];
7
}
8
stack.push(i);
9
}
Временная сложность: O(n)
Каждый элемент добавляется в стек ровно один раз. Каждый элемент удаляется не более одного раза. Итого операций = добавления + удаления ≤ 2n. Так что временная сложность это O(n).
Это драматическое улучшение по сравнению с наивным подходом O(n²).
Пространственная сложность: O(n)
В худшем случае, стек хранит все n индексов (например, если массив в возрастающем порядке). Массив результата также использует O(n) пространства.
Сравнение с наивным подходом:
| Подход | Время | Пространство |
|---|---|---|
| Вложенный цикл (наивный) | O(n²) | O(n) |
| Монотонный стек | O(n) | O(n) |
Для больших массивов, монотонный стек намного быстрее.
В подходе монотонного стека для следующего большего элемента, мы обрабатываем массив в каком направлении?
Когда мы видим новый элемент в монотонном стеке для следующего большего элемента, какие элементы мы удаляем?
Что хранится в монотонном стеке: значения массива или индексы массива?
Для массива [1, 2, 3, 4], какой следующий больший элемент для индекса 0?
Почему подход монотонного стека O(n) вместо O(n²)?
Граничные случаи
Что если есть равные элементы? Формулировка задачи обычно говорит “следующий больший,” что значит строго больший (не равный). В коде, мы используем <= в условии удаления, что гарантирует что равные элементы также удаляются. Если тебе нужен “следующий больший-или-равный,” измени <= на <.
Частая ошибка
“Монотонный стек = всегда возрастающий.” Неправильно. Монотонный стек может быть возрастающий или убывающий. Для следующего большего элемента, мы используем убывающий стек (так что вершина это всегда самый маленький кандидат справа, т.е. следующий больший). Для следующего меньшего элемента, мы используем возрастающий стек.
Ещё практика
Следующие задачи:
- Следующий меньший элемент (NSE): Используй монотонный возрастающий стек.
- Предыдущий больший элемент (PGE): Обработай слева направо с монотонным убывающим стеком, отслеживая индексы слева.
- Самый большой прямоугольник в гистограмме: Классическая задача с монотонным стеком где ты удаляешь когда высота уменьшается, вычисляя площади по дороге. Паттерн похож: держи порядок и удаляй чтобы обнаружить когда ограничение нарушается.
Почему подход монотонного стека работает для поиска следующего большего элемента?
Монотонный стек: список отсортированных кандидатов
-
Что это: Стек что держит элементы в отсортированном порядке (возрастающем или убывающем). Когда ты добавляешь новый элемент, ты сначала удаляешь элементы что нарушают порядок.
-
Инвариант: После каждого добавления, стек отсортирован (например, убывающий для NGE). Это свойство гарантирует что ты держишь только релевантные кандидаты.
-
Следующий больший элемент: Обработай массив справа налево. Удали индексы чьи значения ≤ текущему. Вершина это ответ. Добавь текущий индекс. Результат: O(n) вместо O(n²).
-
Почему O(n): Каждый элемент добавляется один раз и удаляется один раз. Итого операций = O(2n) = O(n).
-
Возрастающий vs. убывающий: Для следующего большего элемента, используй убывающий. Для следующего меньшего элемента, используй возрастающий. Выбор зависит от какого направления тебе нужно.
-
Реальные приложения: Размах акций (Stock span), самый большой прямоугольник в гистограмме, вода в ловушке (Trapping rain water), дневные температуры. Любая задача что спрашивает для следующий/предыдущий элемент удовлетворяющий ограничение это кандидат для монотонного стека.
-
Ключевой insight: Стек это не контейнер общего назначения; это инструмент для эффективной фильтрации и упорядочения кандидатов. Отсортированный инвариант это что делает магию.
Теперь у тебя есть инструменты чтобы решать задачи что наивно кажутся O(n²) но фактически O(n) с умно держимым стеком.