本题旨在分享在刷Leecode过程中发现的一些有趣或者有价值的想法。【当然，答案以js为准】。标题相关原标题标题说明：定义栈的数据结构，请在该类型中实现一个min函数，可以获取栈的最小元素。在这个栈中，调用min、push、pop的时间复杂度为O(1)。MinStackminStack=newMinStack();minStack.push(-2);minStack.push(0);minStack.push(-3);minStack.min();-->返回-3.minStack.pop();minStack.top();-->返回0.minStack.min();-->return-2.//解决框架如下varMinStack=function(){};MinStack.prototype.push=function(x){};MinStack.prototype.pop=function(){};MinStack.prototype.top=function(){};MinStack.prototype.min=function(){};//实际调用示例//varobj=newMinStack()//obj.push(x)思路分析先简单看一下push和pop方法的实现，比较简单，可以用js数组原生的相关方法；其次，top方法只需要返回栈顶元素，也就是数组的最后一个元素，也比较简单；然后，min方法需要获取最小值，时间复杂度要求为O(1)，也就是说我们不能遍历min方法中的数组，必须提前想办法保存起来；并且在push和pop的过程中，需要更新保存的最小值。那么到这里我们就知道了本题的核心难点在于——如何保存当前数据栈的最小值。这里要注意，这个问题要求的是设计一个栈结构，也就是说数据只能单向进出。这是一个非常关键的前提。接下来按照题中的示例步骤，一步步看（仔细看不然一眨眼就过去了！）：最初，数据栈是空的，先把-2压入栈中，此时:datastack[-2]//此时栈中的最小元素值为-2。然后，当0入栈时，此时：datastack[-2,0]//0大于已有的最小值-2，那么最小值还是-2，这里有一个关键点，在当前状态下，元素出栈的方式只能是先出0，再出-2，也就是说-2出栈前，取最小值堆栈中的元素始终为-2。听到这里，是不是心中有什么突兀？！！！.别着急，继续把-3压入栈中。此时：栈中的元素为[-2,0,-3]//最小值应该更新为-3。同理，当-3没有出栈时，栈中的最小值都是-3；当-3出栈时，栈中的最小值应该是前一个最小值-2；然后解决方案就会浮出水面！！！我们只需要多维护一个单调递减的栈，永远只存储当前栈中小于最小值的元素即可！（我知道有些同学看到这里还是不明白，没关系）那我们举个例子吧：//初始状态如下Datastack[-2];最小值栈[-2]；//-2入栈后Datastack[-2];最小值stack[-2];//由于0入栈后0大于-2，所以最小值栈不存-2Datastack[-2,0];Minimumvaluestack[-2];//-3入栈后，-3小于-2，所以最小值stack保存-3数据stack[-2,0,-3];minimumvaluestack[-2,-3];//-3出栈时，比较出栈元素是否为[MinimumValueStack]的栈顶元素，如果是，则一起出栈；数据堆栈[-2,0];最小值栈[-2]；从这里可以看出，最小值栈，一直保持着一个单调递减的数组，栈顶元素（数组末尾的元素）始终代表当前数据栈的最小值。完整代码理解前面的核心内容。其实代码并不难写。最后，粘贴完成的代码：varMinStack=function(){this.dataStack=[];this.minStack=[];};MinStack.prototype。push=function(x){this.dataStack.push(x);constlen=this.minStack.length;如果(len===0||x<=this.minStack[len-1]){this.minStack.push(x);}};MinStack.prototype.pop=function(){constlast=this.dataStack.pop();constlen=this.minStack.length;if(last===this.minStack[len-1]){this.minStack.pop();}};MinStack.prototype.top=function(){constlen=this.dataStack.length;返回len>0？this.dataStack[len-1]:null;};MinStack.prototype.min=function(){constlen=this.minStack.length;返回this.minStack[len-1];};简单又简单的一道题又做了一遍！
