155. 最小栈

思路

这套题我起初用栈+最小堆+延迟删除来做，但是这样没有利用到栈的性质，时间复杂度较高。

实际上，利用好了栈的性质，这题可以用另一个最小栈来存储最小值。

因为栈是先进后出的性质，我们维护这样一个栈来存储最小值，这个栈的栈顶元素是栈当前的最小值。

首先在原始栈入栈时，我们要维护最小栈的性质。判断这个元素是否比栈顶元素小，如果是的话就把这个元素入栈，否则不入。如果栈为空，则直接入栈。这样显然我们在原始栈入栈时成功维护了最小栈的性质。

其次在原始栈出栈时，我们判断该元素是否为最小栈的栈顶元素，如果是则最小栈出栈，否则不出。因为最小栈栈顶元素是当前最小值，如果出栈的元素不是它，则一定比它大，那么我们就不必出栈。这样最小栈的性质也得到了维护。

要想到这个做法，我们要知道栈的性质有很高的顺序性，先进后出，充分利用这个性质，以另一个栈来获取最小元素就是最优解。

Code

class MinStack {
    private Deque<Integer> stack;
    private Deque<Integer> minStack;

    public MinStack() {
        stack = new ArrayDeque<>();
        minStack = new ArrayDeque<>();
    }
    
    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }
    
    public void pop() {
        int val = stack.pop();
        if (val == minStack.peek()) {
            minStack.pop();
        }
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}