跳到主要内容

最小栈

问题​

设计一个支持 push、pop、top 操作，并能在常数时间内检索到最小元素的栈。

  • push(val) — 将元素推入栈
  • pop() — 删除栈顶元素
  • top() — 获取栈顶元素
  • getMin() — 检索栈中最小元素

所有操作的时间复杂度必须为 O(1)O(1)。

示例：

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // 返回 -3
minStack.pop();
minStack.top();    // 返回 0
minStack.getMin(); // 返回 -2

来源：LeetCode 155. 最小栈

答案​

方法一：辅助栈（推荐）​

核心思路：使用两个栈，一个正常栈，一个最小值栈。最小值栈的栈顶始终是当前主栈中的最小值。

MinStack.ts
class MinStack {
  private stack: number[];
  private minStack: number[]; // 同步记录每一步的最小值

  constructor() {
    this.stack = [];
    this.minStack = [Infinity]; // 初始放一个 Infinity 简化逻辑
  }

  push(val: number): void {
    this.stack.push(val);
    // 辅助栈压入当前最小值
    this.minStack.push(Math.min(val, this.minStack[this.minStack.length - 1]));
  }

  pop(): void {
    this.stack.pop();
    this.minStack.pop(); // 同步弹出
  }

  top(): number {
    return this.stack[this.stack.length - 1];
  }

  getMin(): number {
    return this.minStack[this.minStack.length - 1];
  }
}

运行过程：

操作         stack       minStack    getMin
push(-2)    [-2]        [∞, -2]     -2
push(0)     [-2, 0]     [∞, -2, -2] -2
push(-3)    [-2, 0, -3] [∞, -2, -2, -3] -3
pop()       [-2, 0]     [∞, -2, -2] -2
top()       → 0
getMin()    → -2
复杂度分析
  • 时间复杂度：所有操作 O(1)O(1)
  • 空间复杂度：O(n)O(n) — 辅助栈

方法二：只在需要时压入辅助栈（空间优化）​

只有当新值 ≤ 当前最小值时才压入辅助栈：

MinStackOptimized.ts
class MinStack {
  private stack: number[];
  private minStack: number[];

  constructor() {
    this.stack = [];
    this.minStack = [];
  }

  push(val: number): void {
    this.stack.push(val);
    // 只在 val <= 当前最小值时才压入（注意是 <=，不是 <）
    if (this.minStack.length === 0 || val <= this.minStack[this.minStack.length - 1]) {
      this.minStack.push(val);
    }
  }

  pop(): void {
    const val = this.stack.pop()!;
    // 如果弹出的是当前最小值，辅助栈也弹出
    if (val === this.minStack[this.minStack.length - 1]) {
      this.minStack.pop();
    }
  }

  top(): number {
    return this.stack[this.stack.length - 1];
  }

  getMin(): number {
    return this.minStack[this.minStack.length - 1];
  }
}
注意使用小于等于而不是小于

push 时条件必须是 <=（小于等于），因为可能有重复的最小值。如果用 <，pop 时可能提前弹出辅助栈的元素。

方法三：单栈存差值（不使用辅助栈）​

核心思路：不存真实值，存与当前最小值的差值。

MinStackDiff.ts
class MinStack {
  private stack: number[];
  private min: number;

  constructor() {
    this.stack = [];
    this.min = 0;
  }

  push(val: number): void {
    if (this.stack.length === 0) {
      this.stack.push(0);
      this.min = val;
    } else {
      // 存入差值
      this.stack.push(val - this.min);
      if (val < this.min) {
        this.min = val; // 更新最小值
      }
    }
  }

  pop(): void {
    const diff = this.stack.pop()!;
    if (diff < 0) {
      // 差值为负说明当前弹出的是最小值，恢复上一个最小值
      this.min = this.min - diff;
    }
  }

  top(): number {
    const diff = this.stack[this.stack.length - 1];
    if (diff < 0) {
      return this.min; // 差值为负，真实值就是 min
    }
    return this.min + diff; // 差值为正，真实值 = min + diff
  }

  getMin(): number {
    return this.min;
  }
}
差值法原理
  • diff = val - min
  • 如果 diff >= 0：val 不是新的最小值，val = min + diff
  • 如果 diff < 0：val 是新的最小值，旧的 min = val - diff = newMin - diff

这样只用一个栈和一个变量就实现了功能。

注意整数溢出

差值可能超出安全整数范围，JavaScript 中需要注意。在面试中提到这个问题是加分项。

常见面试追问​

Q1: 如何实现最大栈？​

答案：同样的方法，辅助栈改为存最大值：

class MaxStack {
  private stack: number[] = [];
  private maxStack: number[] = [];

  push(val: number): void {
    this.stack.push(val);
    const currMax = this.maxStack.length === 0
      ? val
      : Math.max(val, this.maxStack[this.maxStack.length - 1]);
    this.maxStack.push(currMax);
  }

  pop(): number {
    this.maxStack.pop();
    return this.stack.pop()!;
  }

  getMax(): number {
    return this.maxStack[this.maxStack.length - 1];
  }
}

Q2: 如何用两个栈实现队列？(LeetCode 232)​

答案：

class MyQueue {
  private inStack: number[] = [];
  private outStack: number[] = [];

  push(x: number): void {
    this.inStack.push(x);
  }

  pop(): number {
    this.peek(); // 确保 outStack 有元素
    return this.outStack.pop()!;
  }

  peek(): number {
    if (this.outStack.length === 0) {
      while (this.inStack.length > 0) {
        this.outStack.push(this.inStack.pop()!);
      }
    }
    return this.outStack[this.outStack.length - 1];
  }

  empty(): boolean {
    return this.inStack.length === 0 && this.outStack.length === 0;
  }
}

Q3: 栈在前端的应用场景？​

答案：

  • 浏览器历史记录：前进/后退（两个栈）
  • 撤销/重做：操作栈 + 重做栈
  • 括号匹配：编辑器中的括号高亮
  • 函数调用栈：JavaScript 引擎的执行上下文栈
  • React Fiber：Fiber 架构使用栈来追踪工作进度

相关链接​