前言根据数据结构：“stack”，实现一个min函数，调用该函数获取栈中的最小元素。在这个栈中，调用min、push、pop的时间复杂度为O(1)。相信大部分开发者看到这个问题，第一反应可能是每次入栈时都要对栈中的所有元素进行排序，让最小的元素在栈顶，这样O(1)在时间内得到最小元素。但是这个思路不能保证最后一个入栈的元素能先出栈，所以这个思路行不通。接下来，我们可能会想到用一个变量来存储最小的元素。每次入栈新元素，如果小于当前最小元素，则更新最小元素。这样做的目的是达到了，但是还会有一个问题：如果当前最小的元素出栈了，如何获取下一个最小的元素呢？显然，我们仅仅增加一个变量来存储最小元素是不够的，也就是说，当最小元素被取出时，我们希望得到下一个最小元素。那么，我们是否可以使用一个辅助栈来存储这些最小的元素呢？当一个元素入栈时，我们取出辅助栈中的栈顶元素，与新加入的元素进行比较，将较小的元素压入辅助栈。我们通过一个例子来解释这个过程，如下图：conststack=[3,5,712,1,9,0]入栈的过程如下图所示：出栈时，我们同时弹出两个栈的栈顶元素，在获取最小元素时，我们只返回辅助栈的栈顶元素，流程如下图所示：经过前面分析实现代码，我们已经有了一个完整的思路，接下来就是编码环节了。如下：exportclassStackContainingMinFunctionextendsStack{privateminStack:Stack;私有数据栈：栈；构造函数（）{超级（）;this.minStack=newStack();this.dataStack=newStack();}publicpush(item:number):void{this.dataStack.push(item);如果(this.minStack.size()>0){constminVal=this.minStack.peek();//比较当前push元素和minStack中最小的元素，把小的放入minStackitem>minVal?this.minStack.push(minVal):this.minStack.push(item);返回;}this.minStack.push(item);}publicpop():void{this.minStack.pop();这个.dataStack.pop();}publicmin():数字|空{如果(this.minStack.size()>0)返回this.minStack.peek();返回空值；}}注意：以上代码继承了Stack，我们在上一篇文章中已经实现了，对此感兴趣的开发者请移步：数组实现栈和对象实现栈的区别我们将上一章的例子代入上面实现的功能让我们看看它是否正常工作conststackMinFn=newStackContainingMinFunction();stackMinFn.push(3);stackMinFn.push(5);stackMinFn.push(7);stackMinFn.push(12);stackMinFn.push(1);stackMinFn.push(9);stackMinFn.push(0);stackMinFn.pop();stackMinFn.pop();stackMinFn.pop();console.log("当前栈中最小值为：",stackMinFn.min());示例代码本文所列代码完整版请移步：StackContainingMinFunction.tsstackContainingMinFunction-test.ts
