TypeScript中实现min函数的栈实例，如何详细解析？

本文共计997个文字，预计阅读时间需要4分钟。

目录+前言+思路梳理+实现代码+示例代码+前言+基于数据结构：+栈+实现一个min函数，调用此函数即可获取栈中的最小元素。在该栈中，调用min、push、pop的时间复杂度都为O(1)。+文本内容+

目录

• 前言
• 思路梳理
• 实现代码
• 示例代码

前言

基于数据结构: “栈”，实现一个min函数，调用此函数即可获取栈中的最小元素。在该栈中，调用min、push、pop的时间复杂度都是O(1)。

本文就跟大家分享下这个算法，欢迎各位感兴趣的开发者阅读本文。

思路梳理

相信大多数开发者看到这个问题，第一反应可能是每次往栈中压入一个新元素时，将栈里的所有元素排序，让最小的元素位于栈顶，这样就能在O(1)的时间内得到最小元素了。但这种思路不能保证最后入栈的元素能够最先出栈，因此这个思路行不通。

紧接着，我们可能会想到用一个变量来存放最小的元素，每次压入一个新元素入栈时，如果它比当前最小的元素还要小，则更新最小元素。这样子做目的是达到了，但是又会有另一个问题：如果当前最小元素被弹出栈了，那么如何得到下一个最小的元素？

很显然，我们仅仅添加一个变量用来存储最小元素是不够的，也就是说当最小元素被取出时，我们希望得到次最小元素。那么，我们能否用一个辅助栈专门来存放这些最小元素呢？当元素入栈时，我们就取出辅助栈中的栈顶元素将其与新加入元素做大小比较，把较小的一方压入辅助栈中。