算法1

思路是每次碰到更小的值入栈时，把之前的最小值(min)也先入栈保存。
故出栈时，若当前值为当前最小值，即再次出栈一次的值为更新后的最小值(赋值给min)。 否则，出栈一次即可。
最小值即为变量min;

时间复杂度

每个操作的时间复杂度都是常数。

空间复杂度

仅使用一个栈和普通变量。

参考文献

https://leetcode.com/problems/min-stack/discuss/49014/Java-accepted-solution-using-one-stack

Java代码

class MinStack {

    /** initialize your data structure here. */

    public MinStack() {

    }
    int min=Integer.MAX_VALUE;
    Stack<Integer> stack=new Stack<>();
    public void push(int x) {
        if(x<min){
            stack.push(min);
            min=x;
        }
        stack.push(x);
    }

    public void pop() {
        if(stack.pop()==min)
            min=stack.pop();
    }

    public int top() {
        return stack.peek();

    }

    public int getMin() {
        return min;

    }
}