Leetcode|Leetcode 算法题解系列 - 最小栈 Leetcode算法题解系列-最小栈

本专题旨在分享刷Leecode过程发现的一些思路有趣或者有价值的题目。【当然，是基于js进行解答】。
题目相关

原题地址
题目描述：

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 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.// 解题框架如下 var MinStack = function() {}; MinStack.prototype.push = function(x) {}; MinStack.prototype.pop = function() {}; MinStack.prototype.top = function() {}; MinStack.prototype.min = function() {}; // 实际调用示例 // var obj = new MinStack() // obj.push(x)

思路解析

首先，粗看一下push和pop方法实现比较简单，可以用js数组原生的相关方法进行实现；
其次，top方法只要返回栈顶元素, 也就是数组末位元素，也比较简单；
接着，min方法需要获取最小值，并且要求时间复杂度都是 O(1),这就意味着我们在min方法中，不能去遍历数组，必须想办法提前保存；而且在push和pop过程，需要更新保存的最小值。

那么到这里就知道这个题目的核心难度也就在于-- 如何保存当前数据栈的最小值
这里注意到，题设所要求设计的是栈结构，意味着数据只有单向进出的方式，这是一个很关键的前提。

文章图片

接下来按照题设的例子步骤，一步步来看（认真看不然嗖的一下就过去了！）：

初始时，数据栈为空，首先-2入栈，此时:

数据栈[-2]// 此时栈内最小元素值为-2
接着，0入栈时，此时：

数据栈[-2, 0] // 0 大于已有的最小值-2，那么最小值还是-2，

这里有个关键点，当前状态下，元素出栈的方式，只能是先出0，再出-2，也就是说，在-2出栈之前，栈内元素的最小值始终是-2。听到这，脑海里有没有突然？！！！。

文章图片
别着急，继续入栈-3，此时:

栈内元素为【-2，0，-3】// 最小值应当更新为-3，

同理，当-3没出栈时，栈内最小值都为-3；当-3出栈以后，栈内的最小值应当为先前的一个最小值-2；

那么解法也就浮出水面了！！！

文章图片

我们只需要另外维护一个单调递减的栈，始终只存入比当前栈内最小值更小的元素即可！
(我知道还有部分同学看到这里还是没理解，没关系)那么我们依然举个例子：

// 初始状态如下数据栈[-2]; 最小值栈 [-2]; // -2入栈后数据栈[-2]; 最小值栈 [-2]; // 0入栈后由于0比-2大，因此最小值栈不保存-2 数据栈[-2, 0]; 最小值栈 [-2]; // -3入栈后，-3比-2小，因此最小值栈保存-3 数据栈[-2, 0, -3]; 最小值栈 [-2, -3]; // -3出栈时，比较出栈元素是否是【最小值栈】的栈顶元素，是的话一起出栈；数据栈[-2, 0]; 最小值栈 [-2];

从这里可以看到，最小值栈，一直维护的是一个单调递减的数组，并且栈顶元素（数组末尾元素）始终表示当前数据栈的最小值。
完整代码理解了前面的核心内容，其实代码就不难写了，最后贴上完成代码：

var MinStack = function() { this.dataStack = []; this.minStack = []; }; MinStack.prototype.push = function(x) { this.dataStack.push(x); const len =this.minStack.length; if(len === 0 || x <= this.minStack[len-1]){ this.minStack.push(x); } }; MinStack.prototype.pop = function() { const last = this.dataStack.pop(); const len =this.minStack.length; if(last === this.minStack[len-1]){ this.minStack.pop(); } }; MinStack.prototype.top = function() { const len = this.dataStack.length; return len > 0 ? this.dataStack[len - 1] : null; }; MinStack.prototype.min = function() { const len =this.minStack.length; return this.minStack[len-1]; };

【Leetcode|Leetcode 算法题解系列 - 最小栈】简简单单一道题又搞定了！