我要评论前言
基于数据结构: “栈”，实现一个min函数，调用此函数即可获取栈中的最小元素。在该栈中，调用min、push、pop的时间复杂度都是o(1)。
本文就跟大家分享下这个算法，欢迎各位感兴趣的开发者阅读本文。
思路梳理
相信大多数开发者看到这个问题，第一反应可能是每次往栈中压入一个新元素时，将栈里的所有元素排序，让最小的元素位于栈顶，这样就能在o(1)的时间内得到最小元素了。但这种思路不能保证最后入栈的元素能够最先出栈，因此这个思路行不通。
紧接着，我们可能会想到用一个变量来存放最小的元素，每次压入一个新元素入栈时，如果它比当前最小的元素还要小，则更新最小元素。这样子做目的是达到了，但是又会有另一个问题：如果当前最小元素被弹出栈了，那么如何得到下一个最小的元素？
很显然，我们仅仅添加一个变量用来存储最小元素是不够的，也就是说当最小元素被取出时，我们希望得到次最小元素。那么，我们能否用一个辅助栈专门来存放这些最小元素呢？当元素入栈时，我们就取出辅助栈中的栈顶元素将其与新加入元素做大小比较，把较小的一方压入辅助栈中。
我们通过一个例子来讲解下这个过程，如下所示：
const stack = [ 3, 5, 7 12, 1, 9, 0 ]
入栈过程如下图所示：
出栈时，我们同时弹出两个栈的栈顶元素，获取最小元素时，我们将辅助栈的栈顶元素返回即可，过程如下图所示：
实现代码
经过前面的分析，我们已经得出了完整的思路，接下来就是编码环节了，如下所示：
export class stackcontainingminfunction extends stack {
private minstack: stack;
private datastack: stack;
constructor() {
super();
this.minstack = new stack();
this.datastack = new stack();
}
public push(item: number): void {
this.datastack.push(item);
if (this.minstack.size() > 0) {
const minval = this.minstack.peek();
// 比较当前入栈元素与minstack中的最小元素，将小的一方入minstack
item > minval ? this.minstack.push(minval) : this.minstack.push(item);
return;
}
this.minstack.push(item);
}
public pop(): void {
this.minstack.pop();
this.datastack.pop();
}
public min(): number | null {
if (this.minstack.size() > 0) return this.minstack.peek();
return null;
}
}
注意：上述代码继承了stack，我们在之前文章中已经实现了它，对此感兴趣的开发者请移步：
我们将上个章节的例子代入上述实现的函数中，来看下它能否正确运行。
const stackminfn = new stackcontainingminfunction();
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());
示例代码
本文所列举的代码完整版请移步：
以上就是前端算法之typescript包含min函数的栈实例详解的详细内容，更多关于typescript min函数栈的资料请关注代码网其它相关文章！
发表评论