Стек, очередь и монотонный стек
Интуиция: тарелки и очередь в кофейне
Представь стопку тарелок. Чистую тарелку кладёшь сверху и берёшь тоже сверху. Та, что положили последней, уйдёт первой. Это стек, принцип LIFO (Last In, First Out).
А теперь очередь в кофейне. Кто пришёл первым, того первым и обслужат. Это очередь, принцип FIFO (First In, First Out).
| Структура | Принцип | Добавить | Забрать | Где встречается |
|---|---|---|---|---|
| Стек | LIFO | на вершину | с вершины | «Отменить» в редакторе, вызовы функций, скобки |
| Очередь | FIFO | в хвост | из головы | обход в ширину (BFS), очередь задач |
Обе операции стоят O(1). Больше ничего и не нужно: сила этих структур как раз в ограничениях.
Как это пишется в коде
Стек почти везде делается на динамическом массиве. Для очереди нужна структура, из которой дёшево забирать спереди.
from collections import deque
stack = []
stack.append(1); stack.append(2) # кладём на вершину
top = stack[-1] # смотрим вершину: 2
stack.pop() # снимаем вершину
q = deque()
q.append(1); q.append(2) # в хвост
first = q.popleft() # из головы: 1 (за O(1), в отличие от list.pop(0))Ловушка: в Python
list.pop(0)и в JSarray.shift()работают за O(n), потому что сдвигают весь массив. Для очереди бериdequeили держи индекс головы.
Классика: скобки
Строка "([{}])" корректна, а "([)]" нет. Почему здесь нужен стек? Закрывающая скобка всегда должна совпадать с последней ещё не закрытой открывающей. «Последняя» как раз и означает LIFO.
Идея такая:
- открывающую скобку кладём в стек;
- на закрывающей проверяем, что стек не пуст и на вершине лежит её пара, и снимаем вершину;
- в конце стек должен оказаться пустым.
Это первая задача практики. Попробуй написать её сам по этим трём пунктам, у тебя получится.
Монотонный стек: «следующий больший элемент»
Задача: для каждого числа найти первое число справа, которое больше него, или -1, если такого нет.
Наивное решение для каждого элемента бежит вправо, это O(n²). Можно быстрее.
Интуиция. Представь людей в очереди, и каждый ждёт «кого-то выше себя». Пока такой не пришёл, человек стоит в стеке. Приходит новый и смотрит на вершину стека: если он выше, то он и есть ответ для того, кто там ждёт. Того снимаем, проверяем следующего и так далее. Потом новичок сам встаёт ждать.
В стеке хранятся индексы, а значения по ним идут по убыванию от дна к вершине. Отсюда и название «монотонный».
Состояние перед обработкой 5 (индекс 2): в стеке ждут 2 и 1.
Дальше 3 не больше 5, поэтому просто встаёт в стек. Приходит 6:
В конце в стеке остаются 6 и 4. Справа от них никого больше нет, поэтому у них -1.
Шаблон
def next_greater(nums):
res = [-1] * len(nums)
st = [] # индексы, значения убывают
for i, x in enumerate(nums):
while st and nums[st[-1]] < x: # x больше ждущего → он его ответ
res[st.pop()] = x
st.append(i) # x теперь сам ждёт
return resПочему это O(n), хотя внутри есть while
Вложенный цикл пугает, но давай посчитаем иначе: каждый индекс кладётся в стек ровно один раз и снимается не больше одного раза. Значит, за весь проход случится максимум n push и n pop. Итого O(n) по времени, а стек в худшем случае занимает O(n) памяти. Такой подсчёт называется амортизированным анализом.
Как это звучит на собесе
«Наивно это O(n²). Заметим, что элементы, которые ещё не нашли ответ, образуют убывающую последовательность. Храню их индексы в монотонном стеке. Каждый новый элемент снимает с вершины всех, кто меньше него, и становится их ответом. Каждый индекс входит и выходит из стека максимум раз, поэтому O(n) времени и O(n) памяти».
Частые ошибки
- Хранят значения, а не индексы. Тогда некуда записать ответ, а в задачах «через сколько дней» нечего вычитать.
<против<=. Подумай, считается ли равный элемент «бо́льшим». Знак в условии решает именно это.- Обращение к вершине пустого стека. Всегда сначала проверяй
stна пустоту. - Забыли про остатки. Элементы, оставшиеся в стеке после цикла, получают значение по умолчанию (
-1). - Очередь через
pop(0)/shift(). Решение незаметно превращается в O(n²).
Ты освоил три инструмента: стек, очередь и монотонный стек. Дальше в практике начнём со скобок.