Стек, умеющий возвращать текущий максимум за O(1)

Условие

Необходимо реализовать структуру данных «стек», которая поддерживает следующие операции:

• push(x) — добавить элемент в стек;
• pop() — удалить верхний элемент стека;
• top() — получить значение верхнего элемента без его удаления;
• getMax() — вернуть наибольшее значение среди всех элементов, находящихся в стеке, за константное время.

public class MaxStack {
    public void push(int x) {
        // ...
    }

    public void pop() {
        // ...
    }

    public int top() {
        // ...
    }

    public int getMax() {
        // ...
    }
}

Ответ

В каждой позиции храните пару «значение, максимум до этой позиции». Тогда удаление верхнего элемента автоматически восстанавливает предыдущий максимум.

public class MaxStack {
    private static final class Node {
        final int value, max;
        final Node next;
        Node(int value, int max, Node next) {
            this.value = value; this.max = max; this.next = next;
        }
    }
    private Node head;
    public void push(int x) {
        head = new Node(x, head == null ? x : Math.max(x, head.max), head);
    }
    public void pop() { requireNonEmpty(); head = head.next; }
    public int top() { requireNonEmpty(); return head.value; }
    public int getMax() { requireNonEmpty(); return head.max; }
    private void requireNonEmpty() {
        if (head == null) throw new java.util.NoSuchElementException();
    }
}

Все операции O(1), память O(n). Повторяющиеся максимумы обрабатываются корректно. Список узлов выбран, чтобы push не требовал периодического копирования массива.