本专题旨在分享刷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];};

简简单单一道题又搞定了！