Стек с push, pop и getMax — все за O(1)
Реализуйте коллекцию с тремя операциями, каждая за O(1): push(value) добавляет элемент, pop() удаляет последний добавленный, а getMax() возвращает текущий максимум среди всех хранимых элементов.
Ограничения:
- каждая операция за
O(1), неO(n)— никакого сканирования вgetMax getMaxдолжен оставаться корректным после удаления текущего максимума
class MaxStack {
void push(int value) { /* ваш код здесь */ }
int pop() { /* ваш код здесь */ }
int getMax() { /* ваш код здесь */ }
}Допишите реализацию.
Держите два стека. Основной хранит значения; второй стек max хранит на каждом уровне максимум всего, что было добавлено к этому моменту. В push также кладите max(value, maxStack.peek()) на стек максимумов. В pop снимайте оба. getMax возвращает maxStack.peek(). Поскольку максимум пересчитан и сохранён на каждый элемент, он остаётся корректным после pop, а все три операции — O(1).
- ✗Кешировать единственный максимум, который становится неверным после его удаления
- ✗Брать сортированную структуру, чьи операции на деле не
O(1) - ✗Сканировать элементы в
getMax, делая егоO(n)
- →Почему единственный кешированный максимум ломается после
pop, а парный стек нет? - →Как расширить это, чтобы также возвращать минимум за
O(1)?
Решение
class MaxStack {
private final Deque<Integer> data = new ArrayDeque<>();
private final Deque<Integer> max = new ArrayDeque<>(); // максимум на каждом уровне
void push(int value) {
data.push(value);
max.push(max.isEmpty() ? value : Math.max(value, max.peek()));
}
int pop() {
max.pop();
return data.pop();
}
int getMax() { return max.peek(); }
}Идея. Второй стек хранит «текущий максимум на момент этого push». На каждом push верхушка max — это максимум всех элементов в стеке. Когда элемент снимается, снимается и соответствующая запись max, поэтому верхушка снова отражает максимум оставшихся.
Один кешированный максимум здесь не работает: сняв его, мы не знаем следующий по величине без сканирования. Парный стек хранит историю максимумов, поэтому каждая операция — O(1) и getMax корректен после любого pop.
