155. 最小栈（中等）

第一种方法：

同时在栈中存储当前值，和之前栈中的最小值

class MinStack {
    Stack<Integer> ss;
    public MinStack() {
        ss = new Stack<Integer>();
    }
    
    public void push(int val) {
        if(ss.isEmpty()){
            ss.push(val);
            ss.push(val);
            return;
        }
        int now_min = ss.peek();
        if(now_min < val ){
            ss.push(val);
            ss.push(now_min);
        }else{
            ss.push(val);
            ss.push(val);
        }
        
    }
    
    public void pop() {
        ss.pop();
        ss.pop();
    }
    
    public int top() {
        return ss.get(ss.size()-2);
    }
    
    public int getMin() {
        return ss.peek();
    }
}

第二种方法：

不用额外空间，栈中存储当前值-之前最小值的差值，再更新当前最小值。通过栈中存储的差值，恢复栈中的原有值以及更新之前的最小值。这种方法也没有少用空间，因为他必须要采用Long来存储，但是一个Long相当于2倍的Integer空间了。只是没有利用到两个栈。

class MinStack {

        Integer min = null;
        Stack<Long> data = new Stack<>();

        /**
         * initialize your data structure here.
         */
        public MinStack() {

        }

        public void push(int x) {
            if (data.isEmpty()) {
                data.push(0L);
                min = x;
            } else {
                //如果x是最小的数，这里可能越界，所以用Long来保存
                //需要先计算x-min(之前)的差值，再更新min(当前)=math.min(x,min(之前))；
                data.push(Long.valueOf(x) - min);
                min = Math.min(x, min);
            }
        }

        public void pop() {
            Long diff = data.pop();
            //diff >=0 意味着x-min(之前) >= 0即x >= min(之前)，意味着当前弹出当前x后，不影响min最小值
            if (diff >= 0) {
                //return min + diff;
            } else {
                // diff < 0，意味着 x < min(之前)，意味着弹出x后需要更新最小值min(之前)，
                // 由于x -min(之前) = diff，而x < min(之前)，在push时更新min意味着，x = min(当前)
                // 等式变成：min(当前) -min（之前） = diff，那么min(之前)=min(当前)-diff
                int res = min;
                min = (int) (min - diff);
                //return res;
            }
        }

        public int top() {
            Long diff = data.peek();
            // 如果diff >= 0，意味着x-min(之前) >= 0，且min(当前)=min(之前)，栈中元素diff = x-min(之前)
            // 那么当前栈顶的值x = diff+min(之前) = diff+min(当前)
            if (diff >= 0) {
                return (int) (min + diff);
            } else {
                // 如果diff < 0，意味着 x-min(之前) < 0，意味着min(当前) = x，那就相当于
                //栈顶的值x = min(当前)
                return min;
            }
        }

        public int getMin() {
            return min;
        }
    }