包含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.
提示:
各函数的调用总次数不超过 20000 次

思路:

可以在每个元素 n 入栈时把当前栈的最小值 m 存储起来。在这之后无论何时，如果栈顶元素是 n，我们就可以直接返回存储的最小值 m。

算法:

按照上面的思路，我们只需要设计一个数据结构，使得每个元素 a 与其相应的最小值 m 时刻保持一一对应。因此我们可以使用一个辅助栈，与元素栈同步插入与删除，用于存储与每个元素对应的最小值。

• 当一个元素要入栈时，我们取当前辅助栈的栈顶存储的最小值，与当前元素比较得出最小值，将这个最小值插入辅助栈中；
• 当一个元素要出栈时，我们把辅助栈的栈顶元素也一并弹出；
• 在任意一个时刻，栈内元素的最小值就存储在辅助栈的栈顶元素中。

class MinStack {
    Deque<Integer> xStack;
    Deque<Integer> minStack;
    /** initialize your data structure here. */
    public MinStack() {
        xStack = new LinkedList<Integer>();
        minStack = new LinkedList<Integer>();
        minStack.push(Integer.MAX_VALUE);
    }
  
    public void push(int x) {
        xStack.push(x);
        minStack.push(Math.min(minStack.peek(), x));
    }
  
    public void pop() {
        xStack.pop();   
        minStack.pop();
    }
  
    public int top() {
        return xStack.peek();
    }
  
    public int min() {
        return minStack.peek();
    }
}

参考链接：https://leetcode.cn/problems/bao-han-minhan-shu-de-zhan-lcof/solution/bao-han-minhan-shu-de-zhan-by-leetcode-s-i2fk/