Реализация стека с `push`, `pop`, `peekMax` за O(1)

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

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

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

Код:

// Реализовать стек с поддержкой максимума за O(1)

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

Подсказки

💡 Используй два стека.
💡 Первый стек хранит добавленные значения.
💡 Второй хранит максимальное значение для каждого уровня.
💡 При удалении элемента удаляй значение из обоих стеков.

Решение

public class MaxStack {

    private final Deque<Integer> values = new ArrayDeque<>();
    private final Deque<Integer> maximums = new ArrayDeque<>();

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

        int currentMaximum = maximums.isEmpty()
                ? value
                : Math.max(value, maximums.peek());

        maximums.push(currentMaximum);
    }

    public int pop() {
        checkNotEmpty();

        maximums.pop();
        return values.pop();
    }

    public int peekMax() {
        checkNotEmpty();
        return maximums.peek();
    }

    private void checkNotEmpty() {
        if (values.isEmpty()) {
            throw new NoSuchElementException("Stack is empty");
        }
    }
}

Для каждого элемента в дополнительном стеке хранится максимум на текущей глубине.

Пример:

values:    [5, 2, 7, 3]
maximums:  [5, 5, 7, 7]

После удаления 3 максимальным останется 7. После удаления 7 максимумом снова станет 5.

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

push() — O(1);
pop() — O(1);
peekMax() — O(1);
дополнительная память — O(n).