Стек с поддержкой максимума

Реализовать структуру данных "стек", поддерживающую следующие операции:

• push(x) — добавить элемент в стек
• pop() — удалить верхний элемент
• top() — вернуть верхний элемент
• getMax() — вернуть максимальный элемент среди всех находящихся в стеке (работает за O(1))

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

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

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

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