Что такое monotonic stack?
На этой странице
Monotonic stack - стек, который поддерживает элементы в монотонном порядке. Он нужен для задач "следующий больший/меньший элемент", histogram, temperatures и удаления лишних элементов.
Вопрос
Что такое monotonic stack и какие задачи он решает за O(n)?
Идея
Стек хранит кандидатов в порядке:
increasing или decreasingКогда приходит новый элемент, мы выталкиваем элементы, которые больше не могут быть ответом.
Next greater element
function nextGreater(nums: number[]): number[] {
const result = new Array(nums.length).fill(-1)
const stack: number[] = []
for (let i = 0; i < nums.length; i++) {
while (stack.length > 0 && nums[i] > nums[stack[stack.length - 1]]) {
const index = stack.pop()!
result[index] = nums[i]
}
stack.push(i)
}
return result
}В стеке лежат индексы элементов, для которых следующий больший еще не найден. Значения по этим индексам убывают от дна стека к вершине - отсюда название "монотонный". Пример nums = [2, 1, 3, 2, 4]:
| i | nums[i] | Кого выталкиваем (ответ = nums[i]) | stack после (значения) | result |
|---|---|---|---|---|
| 0 | 2 | никого | [2] | [-1, -1, -1, -1, -1] |
| 1 | 1 | никого, 1 < 2 | [2, 1] | без изменений |
| 2 | 3 | 1, затем 2 | [3] | [3, 3, -1, -1, -1] |
| 3 | 2 | никого | [3, 2] | без изменений |
| 4 | 4 | 2, затем 3 | [4] | [3, 3, 4, 4, -1] |
Для 4 больший так и не нашелся - остался -1.
Каждый индекс попадает в стек и выходит из него не более одного раза.
Сложность:
Time: O(n)
Space: O(n)Когда узнавать паттерн?
- next greater;
- next smaller;
- previous greater;
- daily temperatures;
- largest rectangle in histogram;
- remove duplicate letters;
- "найти ближайший элемент слева/справа".
Что отвечать на собеседовании?
Monotonic stack хранит элементы в возрастающем или убывающем порядке. Когда новый элемент нарушает порядок, мы извлекаем элементы из стека и часто находим для них ответ. Хотя внутри есть while, каждый элемент добавляется и удаляется максимум один раз, поэтому сложность обычно O(n).
Что важно помнить: частые ошибки
- Хранить значения, когда нужны индексы.
- Не понимать, почему
whileне делаетO(n^2). - Путать increasing и decreasing stack.
- Забывать заполнить default answer.
- Ошибаться в сравнении
>/>=.
Мини-шпаргалка
- Stack + порядок.
- Часто храним индексы.
- Каждый элемент push/pop один раз.
- Time обычно
O(n). - Next greater - классика.
- Важно выбрать знак сравнения.