Реализация стека с поддержкой получения минимума за O(1)

24. Реализовать стек с получением минимума за O(1)

Условие задачи:
Необходимо реализовать класс MinStack, который поддерживает операции:

void push(int x) — добавить элемент в стек;
int pop() — удалить и вернуть верхний элемент;
int top() — вернуть верхний элемент без удаления;
int peekMin() — вернуть минимальный элемент стека за O(1).

Все перечисленные операции должны выполняться за O(1).

Код:

public class MinStack {
    // TODO
}

Спойлеры к решению

Подсказки

💡 Используй два стека: один для исходных значений, второй — для текущих минимумов.
💡 При каждом push() сохраняй во втором стеке минимум для текущего состояния.
💡 Тогда верхушка второго стека всегда будет содержать минимальное значение.
💡 При pop() необходимо удалить верхний элемент из обоих стеков.

Решение

public class MinStack {

    private final Deque<Integer> stack = new ArrayDeque<>();
    private final Deque<Integer> minStack = new ArrayDeque<>();

    public void push(int value) {
        stack.push(value);

        if (minStack.isEmpty()) {
            minStack.push(value);
        } else {
            minStack.push(Math.min(value, minStack.peek()));
        }
    }

    public int pop() {
        if (stack.isEmpty()) {
            throw new NoSuchElementException("Стек пуст");
        }

        minStack.pop();
        return stack.pop();
    }

    public int top() {
        if (stack.isEmpty()) {
            throw new NoSuchElementException("Стек пуст");
        }

        return stack.peek();
    }

    public int peekMin() {
        if (minStack.isEmpty()) {
            throw new NoSuchElementException("Стек пуст");
        }

        return minStack.peek();
    }
}

Во втором стеке на каждой позиции хранится минимальное значение для соответствующего состояния основного стека.

Например, после:

minStack.push(Math.min(value, minStack.peek()));

для последовательности:

push(5)
push(2)
push(4)
push(1)

стеки будут выглядеть так:

stack:    [1, 4, 2, 5]
minStack: [1, 2, 2, 5]

Поэтому текущий минимум всегда находится на вершине:

return minStack.peek();

При удалении элемента удаляется и соответствующее значение минимума:

minStack.pop();
return stack.pop();

Пример:

MinStack stack = new MinStack();

stack.push(5);
stack.push(2);
stack.push(4);

System.out.println(stack.peekMin()); // 2

stack.push(1);

System.out.println(stack.peekMin()); // 1

stack.pop();

System.out.println(stack.peekMin()); // 2
System.out.println(stack.top());     // 4

Сложность операций:

push() — O(1);
pop() — O(1);
top() — O(1);
peekMin() — O(1).

Дополнительная память — O(n).

Для реализации стека используется ArrayDeque, поскольку для новых реализаций в Java он обычно предпочтительнее устаревшего класса Stack.