图解LeetCode——剑指 Offer 30. 包含min函数的栈

一、题目

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

二、示例

2.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 次

三、解题思路

3.1> 维护不完整的有序栈

根据题目描述，我们需要定义一个栈结构stack，来支持实现MinStack类的push()、pop()和top()方法。

但是对于min()方法来说，它是用来返回当前堆栈中最小元素的，那么我们可以再创建一个栈结构stackOrder，用来保存一个“不完整”的有序栈，其存储规则如下所示：

• • 当新元素x 小于/等于 stackOrder的栈顶元素时，元素x可以保存到stackOrder的栈顶。
• • 当新元素x 大于 stackOrder的栈顶元素时，元素x不执行入栈操作。

那么通过如上规则，stackOrder中的元素就是从栈顶开始，自上而下逐一变大的，而栈顶就是当前最小的元素。

我们讲完了入栈规则，那么出栈呢？针对于stackOrder来说，出栈规则如下所示：

• • 当stack的栈顶元素 等于 stackOrder的栈顶元素 时，stack和stackOrder的栈顶元素都出栈。
• • 当stack的栈顶元素 不等于 stackOrder的栈顶元素 时，只有stack的栈顶元素出栈。

好了，基本解题思路描述完毕了，下面我们举例，分别入栈-2、0和-3，然后再执行3次出栈操作，再来看一下stack和stackOrder是如何处理的。具体逻辑如下所示：

3.2> 利用元素记录“入栈那一刻”的最小值

那么除了上面的解题思路外，我们其实也可以创建一个Node节点，里面具有如下3个属性：

• • 【int value】当前元素的值；
• • 【int min】当前所有入栈元素中，最小的值；
• • 【Node pre】前一个入栈元素节点；

那么，针对MinStack类的push()、pop()和top()方法，我们就可以通过构建一个Node链表来实现底层逻辑。而针对min()方法来说，因为每个Node节点都保存了它入栈之前所有入栈元素中，最小的值min，所以直接返回当前节点的min值就可以了。此处就不画图了，具体逻辑可以看下面4.2的源码实现部分。

四、代码实现

4.1> 维护不完整的有序栈

class MinStack {
    private Deque<Integer> stack, stackOrder;
    public MinStack() {
        stack = new ArrayDeque<>();
        stackOrder = new ArrayDeque<>();
    }
    public void push(int x) {
        stack.addLast(x);
        if (stackOrder.isEmpty() || min() >= x) stackOrder.addLast(x);
    }
    public void pop() {
        int x = stack.removeLast();
        if (min() == x) stackOrder.removeLast();
    }
    public int top() {return stack.getLast();}
    public int min() {return stackOrder.getLast();}
}

4.2> 利用元素记录“入栈那一刻”的最小值

class MinStack {
    public Node top;
    public MinStack() {}
    public void push(int x) {
        top = new Node(x, top == null ? x : Math.min(x, top.min), top);
    }
    public void pop() {top = top.pre;}
    public int top() {return top.value;}
    public int min() {return top.min;}
}
class Node {
    public int value, min;
    public Node pre;
    public Node(int value, int min, Node pre) {
        this.value = value;
        this.min = min;
        this.pre = pre;
    }
}