155. Min Stack

class MinStack {

    private final Stack<Integer> stack;
    private final Stack<Integer> decreaseStack; // 自底向上非严格单调递减栈

    public MinStack() {
        this.stack = new Stack<>();
        this.decreaseStack = new Stack<>();
    }

    public void push(int val) {
        stack.push(val);
        if (decreaseStack.isEmpty() || val <= decreaseStack.peek()) {
            decreaseStack.push(val);
        }
    }

    public void pop() {
        int val = stack.pop();
        if (decreaseStack.peek() == val) {
            decreaseStack.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return decreaseStack.peek();
    }

}

References

155. Min Stack
剑指 Offer 30. 包含min函数的栈