包含min函数的栈

1、题目

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 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.

2、思路

普通栈的 push() 和 pop() 函数的复杂度为 O(1) ；而获取栈最小值 min() 函数需要遍历整个栈，复杂度为 O(N)。

1、要将 min() 函数复杂度降为 O(1)，可以用空间换时间，用一个单独的栈来辅助实现查询最小值。即除在A栈正常进行入栈出栈操作时，对每次进栈的元素与B栈的栈顶元素比较，使B栈的栈顶元素始终为最小值。

2、要使元素出栈后，当该元素恰为最小元素时，B栈取的栈顶元素仍为A栈中剩余元素中的最小元素，故在执行pop()时，应与B栈的栈顶元素比较。

复杂度分析：

时间复杂度 O(1) ： push(), pop(), top(), min() 四个函数的时间复杂度均为常数级别。

空间复杂度 O(N) ： 当共有 N 个待入栈元素时，辅助栈 B 最差情况下存储 N个元素，使用 O(N)额外空间。

3、代码

class MinStack {
    Stack<Integer> A, B;
    public MinStack() {
        A = new Stack<>();
        B = new Stack<>();
    }
    public void push(int x) {
        A.add(x);
        if(B.empty() || B.peek() >= x){
            B.add(x);
        }
    }
    public void pop() {
        if(A.pop().equals(B.peek())){
            B.pop();
        }
    }
    public int top() {
        return A.peek();
    }
    public int min() {
        return B.peek();
    }
}