算法 - 最小栈（Min Stack）

Posted on

1. 题目

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

实现 MinStack 类：

  • push(val) 将元素压入栈
  • pop() 移除栈顶元素
  • top() 返回栈顶元素
  • getMin() 返回栈中的最小元素

示例:

1
2
3
4
5
6
7
8
9
输入:
MinStack s = new MinStack();
s.push(-2);
s.push(0);
s.push(-3);
s.getMin();   → -3
s.pop();
s.top();      → 0
s.getMin();   → -2

2. 解题思路

普通栈取最小值需要 O(n) 遍历。要 O(1)，需额外空间换时间。

2.1 辅助栈（同步记录最小值）

维护两个栈：data 存所有元素，minStack 存「对应 data 各状态下的最小值」。

  • push 时：data 正常入栈；minStack 入栈 min(val, 当前 minStack 栈顶)。
  • pop 时：两栈同时弹出。
  • getMin：直接看 minStack 栈顶。

这样 minStack 栈顶始终是 data 当前全部元素的最小值。

  • 时间复杂度：所有操作 O(1)；空间复杂度：O(n)。

2.2 优化：最小栈只在「新最小或并列最小」时压入

minStack 只在 val <= 当前最小 时压入，pop 时若 data 弹出值等于栈顶再同步弹出 minStack，可省部分空间（注意 <= 以处理重复最小值）。

3. TypeScript 实现

3.1 双辅助栈（经典）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class MinStack {
    private data: number[] = [];
    private minStack: number[] = [];

    push(val: number): void {
        this.data.push(val);
        const curMin = this.minStack.length
            ? this.minStack[this.minStack.length - 1]
            : val;
        this.minStack.push(Math.min(val, curMin));
    }

    pop(): void {
        this.data.pop();
        this.minStack.pop();
    }

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

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

3.2 单栈存差值（进阶，省一个栈）

栈中每个元素存「压入时的值 − 当时的最小值」。用 min 记录当前最小：

  • 压入 val：若 val - min >= 0 直接入栈；否则说明出现更小值，入 val - min（负数）并更新 min = val。
  • pop 时：弹出 d，若 d >= 0 原值为 min + d；若 d < 0 说明弹出的是「旧的最小值」，需还原 min = min - d。

思路巧妙但边界易错，面试能讲清 3.1 已足够，3.2 作为加分。

4. 面试延伸

  • 核心思想：用空间换 O(1) 查询，「辅助栈记录历史状态」是通用技巧。
  • 追问：如果 getMin 之后还要能恢复？——正因为 pop 同步回退 minStack，历史最小值可正确还原，这是辅助栈方法的正确性来源。
  • 类似设计题：LRU 缓存、带最大值的队列（双栈模拟队列 + 单调队列）等，考察数据结构组合能力，可对照本博客 LRU Cache。
  • 语言细节：TS 里 private 字段、返回栈顶用 arr[arr.length-1]，注意空栈的防御（LeetCode 保证合法调用）。

难度：中等 | LeetCode 155 | 设计 / 栈