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

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

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

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

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

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

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