[LeetCode]（面试题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.

提示：

1. 各函数的调用总次数不超过 20000 次

解题思路

设计一个元素栈用来插入删除元素，一个辅助栈用来存储与每个元素对应的最小值，使得每个元素 a 与其相应的最小值 m 时刻保持对应。

具体步骤：
1）当一个元素要入栈时，先将它插入元素栈，这时如果辅助栈为空，则直接插入；如果非空，取当前辅助栈的栈顶存储的最小值，与当前元素比较得出新的最小值，将这个新的最小值再插入辅助栈中；
2）当一个元素要出栈时，元素栈与辅助栈的栈顶元素一并弹出；
3）在任意时刻，辅助栈的栈顶元素就是栈内元素的最小值。

复杂度分析：
时间复杂度：对于题目中的所有操作，时间复杂度均为 O(1)。因为栈的插入、删除与读取操作都是 O(1)，我们定义的每个操作最多调用栈操作两次。
空间复杂度：O(n)，其中 n 为总操作数。最坏情况下，我们会连续插入 n 个元素，此时两个栈占用的空间为 O(n)。

注：另一种解法可参考 155. 最小栈

代码

class MinStack {
    Deque<Integer> stack;
    Deque<Integer> supstack;

    /** initialize your data structure here. */
    public MinStack() {
        stack = new LinkedList<>();
        supstack = new LinkedList<>();
    }
    
    public void push(int x) {
        stack.push(x);
        if(supstack.isEmpty() || x < supstack.peek()){
            supstack.push(x);
        }else{
            supstack.push(supstack.peek());
        }
    }
    
    public void pop() {
        stack.pop();
        supstack.pop();
    }
    
    public int top() {
        int res = stack.peek();
        return res;
    }
    
    public int min() {
        int min = supstack.peek();
        return min;
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.min();
 */