小九的酒窝

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

• push(x) —— 将元素 x 推入栈中。
• pop() —— 删除栈顶的元素。
• top() —— 获取栈顶元素。
• getMin() —— 检索栈中的最小元素。

给出两种解决方案：
1、辅助栈
思路是使用辅助栈来保存当前节点到之前节点的最小值。代码如下：

    class MinStack {
        //  数据栈
        Deque<Integer> xStack;
        //  辅助栈
        Deque<Integer> minStack;
        //  初始化方法
        public MinStack() {
            xStack = new LinkedList<>();
            minStack = new LinkedList<>();
            minStack.push(Integer.MAX_VALUE);            
        }
        //  入栈
        public void push (int x) {
            xStack.push(x);
            minStack.push(Math.min(minStack.peek(), x));
        }
        //  出栈
        public void pop() {
            xStack.poll();
            minStack.poll();
        }
        //  获取栈顶元素
        public int top() {
            return xStack.peek();
        }
        //  获取最小值
        public int getMin() {
            return minStack.peek();
        }
    }

第二种解法，不使用额外的空间，栈中保存差值。
思路是栈中保存入栈值和最小值的差值。
入栈的时候，计算入栈值和最小值的差值，将其入栈，如果小于0，那么更新最小值。
出栈的时候，如果出栈值小于0，代表这里最小值发生改变，当时入栈的是当前的最小值，出栈值是当前的最小值减去之前的最小值，所以用当前的最小值减去这个差值，就是之前的最小值。
可以理解为，把栈分割成n段，每段他们的最小值是相同的，栈里保存的是入栈的值和当前最小值的差，而段与段的间隔，就是当前最小值入栈的时候，和前一段最小值的差。
这里需要注意一点，就是，不能再使用Integer来记录入栈的数据，因为它有可能超出整型的范围。
代码如下：

    class MinStack {
        //  差值栈
        Deque<Long> xStack;
        //  当前最小值
        Integer minValue;
        public MinStack() {
            xStack = new LinkedList<>();
            minValue = Integer.MAX_VALUE;
        }
        public void push(int x) {
            //  差值栈空了 当前没有数据进来
            if (xStack.isEmpty()) {
                xStack.push(0L);
                minValue = x;
            } else {
                xStack.push((long)x - minValue);
                minValue = Math.min(minValue, x);
            }
        }
        public void pop() {
            long diff = xStack.pop();
            if (diff < 0) {
                //  这里pop出minValue
                minValue = (int)(minValue - diff);
            } else {
                //  这里pop出minValue+diff
            }
        }
        public int top() {
            long diff = xStack.peek();
            if (diff < 0) {
                return minValue;
            } else {
                return (int)(minValue+diff);
            }
        }
        public int getMin() {
            return minValue;
        }
    }