Min Stack — это стек, который умеет не только обычные операции:
push
pop
top
но ещё и операцию:
getMin
причём getMin() должен работать за O(1).
То есть задача такая:
добавить элемент O(1)
удалить верхний O(1)
посмотреть верхний O(1)
узнать минимум в стеке O(1)
Обычный стек умеет быстро доставать только верхний элемент.
Например:
stack = [5, 3, 7, 2, 6]
top() быстро вернёт 6.
Но если спросить:
какой минимум в стеке?
обычный стек сам по себе не знает. Нужно пройти все элементы:
5, 3, 7, 2, 6
и найти 2.
Это было бы:
O(n)
А Min Stack требует:
getMin() -> O(1)
Значит минимум надо как-то хранить заранее.
Главная идея
Мы храним два стека:
main stack — обычные значения
min stack — текущие минимумы
main stack хранит всё:
[5, 3, 7, 2, 6]
min stack хранит минимумы, которые актуальны на разных уровнях стека:
[5, 3, 2]
То есть когда появляется новый минимум, мы кладём его в min stack.
Пример пошагово
Делаем:
push(5)
push(3)
push(7)
push(2)
push(6)
push(5)
main = [5]
min = [5]
Минимум сейчас 5.
push(3)
3 меньше 5, значит это новый минимум.
main = [5, 3]
min = [5, 3]
Минимум сейчас 3.
push(7)
7 не меньше текущего минимума 3, значит в min не добавляем.
main = [5, 3, 7]
min = [5, 3]
Минимум всё ещё 3.
push(2)
2 меньше 3, это новый минимум.
main = [5, 3, 7, 2]
min = [5, 3, 2]
Минимум сейчас 2.
push(6)
6 не меньше 2.
main = [5, 3, 7, 2, 6]
min = [5, 3, 2]
Теперь:
getMin() -> верхушка min stack -> 2
Без прохода по всему стеку.
Что происходит при pop
Допустим:
main = [5, 3, 7, 2, 6]
min = [5, 3, 2]
Делаем:
pop()
Удаляется 6.
6 не был минимумом, значит min stack не трогаем.
main = [5, 3, 7, 2]
min = [5, 3, 2]
Теперь ещё раз:
pop()
Удаляется 2.
А 2 был текущим минимумом. Значит его надо удалить и из min stack.
main = [5, 3, 7]
min = [5, 3]
Теперь минимум снова 3.
Вот в этом вся механика.
Важный момент с дубликатами
Вот здесь есть маленькая ловушка.
Допустим:
push(5)
push(3)
push(3)
push(7)
Если в min stack класть новый минимум только когда x < currentMin, то второй
3 туда не попадёт.
Но потом если удалить один 3, можно случайно потерять минимум, хотя второй
3 ещё остался в основном стеке.
Поэтому часто делают так:
если x <= текущего минимума,
добавляем x в min stack
То есть не строго меньше, а меньше или равно.
Пример:
main = [5, 3, 3, 7]
min = [5, 3, 3]
Теперь если удалить верхний 3, в min stack останется ещё один 3.
Это правильно.
Python
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val: int) -> None:
self.stack.append(val)
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self) -> None:
val = self.stack.pop()
if val == self.min_stack[-1]:
self.min_stack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.min_stack[-1]
Java
import java.util.*;
class MinStack {
private Deque<Integer> stack;
private Deque<Integer> minStack;
public MinStack() {
stack = new ArrayDeque<>();
minStack = new ArrayDeque<>();
}
public void push(int val) {
stack.push(val);
if (minStack.isEmpty() || val <= minStack.peek()) {
minStack.push(val);
}
}
public void pop() {
int val = stack.pop();
if (val == minStack.peek()) {
minStack.pop();
}
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
Почему все операции O(1)
push -> кладём в один или два стека -> O(1)
pop -> удаляем из одного или двух стеков -> O(1)
top -> смотрим верхушку main stack -> O(1)
getMin -> смотрим верхушку min stack -> O(1)
Память:
O(n)
Потому что в худшем случае min_stack может хранить почти столько же элементов,
сколько и основной стек.
Например:
push(5)
push(4)
push(3)
push(2)
push(1)
Каждый новый элемент — новый минимум.
main = [5, 4, 3, 2, 1]
min = [5, 4, 3, 2, 1]
Это не monotonic stack
Вот важное различение.
Monotonic stack обычно используется, чтобы искать:
next greater
next smaller
previous greater
previous smaller
Там стек хранит кандидатов и выкидывает тех, кто больше не нужен.
А Min Stack — это другая идея:
обычный стек + дополнительная история минимумов
То есть Min Stack не ищет «следующий меньший элемент». Он просто поддерживает
быстрый ответ на вопрос:
какой минимум сейчас лежит внутри стека?
Интуитивная формула
Обычный стек:
верхний элемент
Min Stack:
верхний элемент + текущий минимум
min_stack — это как память о том, каким был минимум на каждом важном уровне
глубины.
Мы не пересчитываем минимум после каждого pop, а просто откатываемся к
предыдущему минимуму, потому что он уже лежит ниже в отдельном стеке.
