共计 2074 个字符，预计需要花费 6 分钟才能阅读完成。
本专题旨在分享刷 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];
};简简单单一道题又搞定了！