155. 最小栈

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

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

示例:

输入：
["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.

提示：

pop、top 和 getMin 操作总是在 非空栈 上调用。

解题思路1：这道题虽然标的是easy，但感觉是medium难度的题目，第一种解法使用两个栈，一个栈完成正常的栈功能，对所有的元素进行常规操作，第二个栈在push的过程中，始终保留着当前为止的最小值，如果第二个栈为空或者当前加入的元素小于等于第二个栈栈顶元素，说明有更小的数进来了，因此把这个新进来的元素也压入第二个栈，这样第二个栈的栈顶始终保留着第一个栈中所有元素中的最小值，而当pop操作的时候，如果pop出来的元素刚好和第二个栈的栈顶元素相等，那第二个栈也需要pop一下，表示这个最小元素已经出栈了，有个需要注意的地方就是，如果有两个元素，同时是最小值，那他们也同时都需要push到第二个栈里面，这样pop出来的时候才不会冲突，否则可能出现那种，push进去一个，pop出来两个或者取不到栈顶元素的情况。

代码 t81 s94 java

class MinStack {

    /** initialize your data structure here. */
    public MinStack() {
        s1 = new Stack<>();
        s2 = new Stack<>();
    }
    
    public void push(int val) {
        s1.push(val);
        if(s2.isEmpty() || val<=s2.peek()) s2.push(val);
    }
    
    public void pop() {
        int t = s1.pop();
        if(t==s2.peek()) s2.pop();
    }
    
    public int top() {
        return s1.peek();
    }
    
    public int getMin() {
        return s2.peek();
    }

    private Stack<Integer> s1, s2;
}

解题思路2：这里用的是仅一个栈来解决问题的思路，min初始化为Integer.MAX_VALUE，如果当前push进来的元素比min小，那把min也push进栈里，同时min更新为val，这样做的结果就是，每个被push进去的min和另一个min之间的元素数值都比min要小，而往栈顶走的话就有更小的元素出现了，在pop出来时候，如果pop出来的元素和min相等，说明比这个min小的元素已经全都pop出来了，因此就把再pop出下一段的min值，并赋值给min进行更新。

代码 t97 s15 java

class MinStack {

    /** initialize your data structure here. */
    public MinStack() {}
    
    public void push(int val) {
        if(val<=min){
            st.push(min);
            min = val;
        }
        st.push(val);
    }
    
    public void pop() {
        if(st.pop()==min){
            min = st.pop();
        }
    }
    
    public int top() {
        return st.peek();
    }
    
    public int getMin() {
        return min;
    }

    private Stack<Integer> st = new Stack<>();
    private int min = Integer.MAX_VALUE;
}

参考资料：
http://www.cnblogs.com/grandyang/p/4091064.html

155. 最小栈

原文：https://www.cnblogs.com/zhengxch/p/14719062.html