TypeScript实现包含min函数的栈（O(1)时间复杂度）

作者：纸飞机时间：2026-10-25 20:59:33浏览：250

本文详解如何在TypeScript中实现一个支持min函数的栈。通过引入辅助栈记录历史最小值，确保push、pop和min操作的时间复杂度均为O(1)。文章梳理了错误思路，提供了完整的类实现代码及测试用例，帮助开发者掌握高效栈算法。

前言

本文旨在基于“栈”这一数据结构，实现一个具备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());