30-包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.min();   --> 返回 -2.

最容易想到的方法

首先我们可以考虑将最小元素储存在一个变量里，每次进栈首先判断min和进栈元素大小，始终保持min是最小值，但如果有数据出栈，就麻烦了，因为我们没有记录次小的元素。所以还需要有个容器存储当前栈范围内最小的元素。也就是需要两个栈，一个是数据栈，一个是辅助栈。

    private Stack<Integer> minStack = new Stack<>();//辅助栈
    private Stack<Integer> dataStack = new Stack<>();//数据栈
    public void push(int x) {
        dataStack.push(x);
        if (minStack.isEmpty()) {//如果minStack是空，那么直接入栈即可。
            minStack.push(x);
        }else{ //假如当前minStack的栈顶元素比x要大，说明x进入数据栈之后，最小的元素应该是x了，所以x进辅助栈；否则说明最小元素还是minStack的栈顶元素，重复进栈。这里我们可以看到，minStack的元素数量和dataStack始终保持一致，minStack的栈顶元素就是当前数据栈中的最小元素。
            int top = minStack.peek();
            if (x < top) {
                minStack.push(x);
            }else{
                minStack.push(top);
            }
        }
    }

    public void pop() {
        minStack.pop();
        dataStack.pop();
    }

    public int top() {
        return dataStack.peek();
    }

    public int min() {
        return minStack.peek();
    }

优化空间使用

实际上辅助栈的元素数量不必和数据栈完全一样，辅助栈的栈顶元素就是当前数据栈的最小元素。

我们只要在进栈的时候控制：

1. 如果当前辅助栈为空，那么直接进栈
2. 如果当前辅助栈不为空，那么比较下入栈元素与辅助栈栈顶元素，只有入栈元素<=辅助栈栈顶元素时，才有必要入栈。

出栈时控制：

1. 如果出栈元素与当前辅助栈栈顶元素相同，那么辅助栈也需要弹出栈顶元素，否则就不用弹出了。

private Stack<Integer> minStack = new Stack<>();
    private Stack<Integer> dataStack = new Stack<>();

    public void push(int x) {
        dataStack.push(x);
        if(minStack.isEmpty() || minStack.peek() >= x){
            minStack.add(x);
        }
    }

    public void pop() {
        Integer data = dataStack.pop();
        if (data.equals(minStack.peek())) {//如果相等，说明需要将minStack栈顶元素也弹出
            minStack.pop();
        }
    }

    public int top() {
        return dataStack.peek();
    }

    public int min() {
        return minStack.peek();
    }