155. 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

• MinStack() 初始化堆栈对象。
• void push(int val) 将元素val推入堆栈。
• void pop() 删除堆栈顶部的元素。
• int top() 获取堆栈顶部的元素。
• int getMin() 获取堆栈中的最小元素。

示例 1:

输入：

["MinStack","push","push","push","getMin","pop","top","getMin"]

[[],[-2],[0],[-3],[],[],[],[]]

输出：

[null,null,null,null,-3,null,0,-2]

解释：

MinStack minStack = new MinStack();

minStack.push(-2);

minStack.push(0);

minStack.push(-3);

minStack.getMin(); --> 返回 -3.

minStack.pop(); minStack.top(); --> 返回 0.

minStack.getMin(); --> 返回 -2.

思路：可以用一个辅助栈记录当前的最小值，每push一个元素进栈时进行比较，保存和top元素相比较小的那一个。

class MinStack {
    Deque<Integer> xStack;
    Deque<Integer> minStack;

    public MinStack() {
        xStack = new LinkedList<Integer>();
        minStack = new LinkedList<Integer>();
        minStack.push(Integer.MAX_VALUE);
    }
    
    public void push(int x) {
        xStack.push(x);
        minStack.push(Math.min(minStack.peek(), x));
    }
    
    public void pop() {
        xStack.pop();
        minStack.pop();
    }
    
    public int top() {
        return xStack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

上面这种做法的空间复杂度时O(n)，还有一种空间复杂度为O(1)的方法，但官方用例过不了，int最大值相减时会超过32bit。此方法仅供思路参考：

不用一个min辅助栈维护当前的最小值，而是在push元素时比较push的元素和当前最小值的差值(diff = val - minVal)。如果diff小于0，说明当前push的值比当前最小值还小，更新最小值，把diff压入栈中。在进行poll操作时，因为栈记录的是diff，要进行一个还原的操作。如果当前poll值小于0，说明现在移除的是最小值，要更新当前最小值(minVal = minVal - diff)。在获取top元素时，同理，如果top元素小于0，直接返回当前最小值，否则要返回minVal + diff。

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

    public MinStack() {
        stack = new ArrayDeque<>();
    }
    
    public void push(int val) {
        if(stack.isEmpty()){
            minVal = val;
            stack.push(0);
        }else {
            int diff = val - minVal;
            stack.push(diff);
            if(diff < 0){
                minVal = val;
            }
        }
    }
    
    public void pop() {
        Integer val = stack.pop();
        if(val < 0){
            minVal = minVal - val;
        }
    }
    
    public int top() {
        Integer val = stack.peek();
        return val < 0 ? minVal : minVal + val;
    }
    
    public int getMin() {
        return minVal;
    }
}