图解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> 维护不完整的有序栈

classMinStack {
privateDeque<Integer>stack, stackOrder;
publicMinStack() {
stack=newArrayDeque<>();
stackOrder=newArrayDeque<>();
    }
publicvoidpush(intx) {
stack.addLast(x);
if (stackOrder.isEmpty() ||min() >=x) stackOrder.addLast(x);
    }
publicvoidpop() {
intx=stack.removeLast();
if (min() ==x) stackOrder.removeLast();
    }
publicinttop() {returnstack.getLast();}
publicintmin() {returnstackOrder.getLast();}
}

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

classMinStack {
publicNodetop;
publicMinStack() {}
publicvoidpush(intx) {
top=newNode(x, top==null?x : Math.min(x, top.min), top);
    }
publicvoidpop() {top=top.pre;}
publicinttop() {returntop.value;}
publicintmin() {returntop.min;}
}
classNode {
publicintvalue, min;
publicNodepre;
publicNode(intvalue, intmin, Nodepre) {
this.value=value;
this.min=min;
this.pre=pre;
    }
}

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」