155. 最小栈

LeetCode：原题
难度：中等
归类：栈、设计
主解法：同步辅助栈

先给结论

普通栈只能在 O(1) 时间访问栈顶，无法直接知道整个栈的最小值。如果每次 getMin() 都遍历栈，需要 O(n) 时间，不符合题目要求。

解决方法是使用两个同步栈：

dataStack[i]：第 i 个入栈的真实元素；
minStack[i]：入栈前 i + 1 个元素后的最小值。

每次 push 时，把“旧最小值与新元素中的较小者”压入 minStack。两个栈始终同步压入、同步弹出，因此 minStack 的栈顶永远是当前最小值。

minStack 的栈顶 = dataStack 当前全部元素的最小值

四个操作 push、pop、top、getMin 都是 O(1)。

题目描述

设计一个支持以下操作的栈：

push(val)：将元素 val 压入栈；
pop()：删除栈顶元素；
top()：获取栈顶元素；
getMin()：获取栈中的最小元素。

要求所有操作都在 O(1) 时间内完成。

示例：

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

对应操作：

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

问题本质

困难不在普通的入栈、出栈，而在于：最小元素被弹出后，怎样在 O(1) 时间恢复它之前的最小值？

例如：

依次入栈：3、1、2

dataStack = [3, 1, 2]
当前最小值 = 1

弹出 2 后，最小值仍为 1；再弹出 1 后，最小值需要恢复为 3。

如果只用变量 min = 1 保存当前最小值，那么弹出 1 后，并不知道上一个最小值是 3，只能重新扫描剩余元素。说明我们需要保存最小值的历史变化。

辅助栈就是这段历史：它为每个栈深度保存当时的最小值。

核心设计：同步辅助栈

状态定义

假设两个栈的有效元素数量相同：

dataStack[i] = 第 i 个入栈的元素
minStack[i]  = dataStack[0...i] 中的最小值

因此有递推关系：

minStack[i] = min(minStack[i - 1], dataStack[i])

为了省去第一次入栈时的空栈判断，可以给 minStack 放一个哨兵 Infinity：

minStack 初始值：[Infinity]

这样任何正常数字第一次入栈时，都可以统一计算：

min(Infinity, val) = val

核心不变量

完成任意一次操作后，始终满足：

minStack.length === dataStack.length + 1，多出的一个元素是哨兵；
对每个有效下标 i，minStack[i + 1] 等于 dataStack[0...i] 的最小值；
因此 minStack 栈顶就是当前整个数据栈的最小值。

逐步推演

依次执行 push(-2)、push(0)、push(-3)：

初始状态

dataStack：[]
minStack ：[∞]

第 1 步：`push(-2)`

新最小值：

min(∞, -2) = -2

两个栈同步压入：

                栈顶
dataStack：[-2]  ← -2
minStack ：[∞, -2] ← -2

第 2 步：`push(0)`

新元素 0 大于旧最小值 -2，所以最小值仍是 -2：

min(-2, 0) = -2

dataStack：[-2,  0]
minStack ：[∞, -2, -2]
                       ↑
                    当前最小值

注意：即使最小值没有变化，minStack 仍然要压入一个 -2，这样两个栈的层级才能一一对应。

第 3 步：`push(-3)`

min(-2, -3) = -3

dataStack：[-2,  0, -3]
minStack ：[∞, -2, -2, -3]
                            ↑
                         当前最小值

所以 getMin() 直接返回 minStack 栈顶 -3。

第 4 步：`pop()`

两个栈同步弹出：

弹出前：
dataStack：[-2,  0, -3]
minStack ：[∞, -2, -2, -3]

弹出后：
dataStack：[-2,  0]
minStack ：[∞, -2, -2]
                       ↑
                    最小值自动恢复为 -2

不需要重新扫描 dataStack，因为上一个深度对应的最小值已经保存在 minStack 中。

代码实现

JavaScript：同步双栈

var MinStack = function () {
    // 保存实际入栈的元素
    this.dataStack = [];
    // 栈顶保存当前最小值；Infinity 是处理第一次 push 的哨兵
    this.minStack = [Infinity];
};

/**
 * @param {number} val
 * @return {void}
 */
MinStack.prototype.push = function (val) {
    this.dataStack.push(val);

    // 当前最小值 = 旧最小值与新元素中的较小者
    const previousMin = this.minStack[this.minStack.length - 1];
    this.minStack.push(Math.min(previousMin, val));
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function () {
    // 两个栈必须同步弹出，保持每一层一一对应
    this.dataStack.pop();
    this.minStack.pop();
};

/**
 * @return {number}
 */
MinStack.prototype.top = function () {
    return this.dataStack[this.dataStack.length - 1];
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function () {
    // 辅助栈栈顶始终是数据栈当前全部元素的最小值
    return this.minStack[this.minStack.length - 1];
};

/**
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(val)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.getMin()
 */

代码与思路对照

操作	`dataStack`	`minStack`	时间复杂度
`push(val)`	压入 `val`	压入 `min(旧最小值, val)`	`O(1)`
`pop()`	弹出栈顶	同步弹出栈顶	`O(1)`
`top()`	返回栈顶	不变	`O(1)`
`getMin()`	不访问	返回栈顶	`O(1)`

正确性证明

对数据栈中的元素数量进行归纳。

初始状态

数据栈为空，辅助栈只有哨兵 Infinity，不变量成立。

执行 `push(val)`

假设入栈前，辅助栈顶是数据栈的最小值 oldMin。入栈后，整个数据栈的最小值只可能是：

min(oldMin, val)

代码把这个值压入辅助栈，所以新的辅助栈顶等于新的全局最小值，不变量继续成立。

执行 `pop()`

两个栈同步弹出，回到入栈前的同一层。辅助栈露出的栈顶正是该层原先保存的最小值，因此不变量继续成立。

top() 和 getMin() 都不会修改状态。由归纳可知，任意操作后辅助栈顶都等于数据栈的最小值，所以所有操作正确。

重复最小值为什么容易出错

考虑：

push(2)
push(1)
push(1)

同步辅助栈保存为：

dataStack：[2, 1, 1]
minStack ：[∞, 2, 1, 1]

弹出一个 1 后：

dataStack：[2, 1]
minStack ：[∞, 2, 1]

最小值仍然是 1。

如果采用“只有新元素严格小于当前最小值时才压入辅助栈”的写法，第二个 1 不会被记录；弹出它时却可能错误地同时删除唯一的最小值记录。因此：

同步辅助栈方案：每次都压入当前最小值，没有特殊判断；
压缩辅助栈方案：新元素必须在 val <= currentMin 时压入，等于时也要记录。

替代方案一：辅助栈只记录最小值变化

辅助栈不必和数据栈等长，也可以只保存成为过最小值的元素：

var MinStack = function () {
    this.dataStack = [];
    this.minStack = [];
};

MinStack.prototype.push = function (val) {
    this.dataStack.push(val);

    // 必须使用 <=，确保重复最小值也被记录
    if (
        this.minStack.length === 0 ||
        val <= this.minStack[this.minStack.length - 1]
    ) {
        this.minStack.push(val);
    }
};

MinStack.prototype.pop = function () {
    const removed = this.dataStack.pop();

    // 只有被删除元素等于当前最小值时，才删除一层最小值记录
    if (removed === this.minStack[this.minStack.length - 1]) {
        this.minStack.pop();
    }
};

MinStack.prototype.top = function () {
    return this.dataStack[this.dataStack.length - 1];
};

MinStack.prototype.getMin = function () {
    return this.minStack[this.minStack.length - 1];
};

这个方案可能节省空间，但分支更多，尤其容易漏掉重复最小值。同步辅助栈更适合面试时快速写出可靠代码。

替代方案二：单栈存二元组

还可以让每个栈元素同时保存“真实值”和“入栈后的最小值”：

var MinStack = function () {
    this.stack = [];
};

MinStack.prototype.push = function (val) {
    const currentMin =
        this.stack.length === 0
            ? val
            : Math.min(this.stack[this.stack.length - 1].min, val);

    this.stack.push({ value: val, min: currentMin });
};

MinStack.prototype.pop = function () {
    this.stack.pop();
};

MinStack.prototype.top = function () {
    return this.stack[this.stack.length - 1].value;
};

MinStack.prototype.getMin = function () {
    return this.stack[this.stack.length - 1].min;
};

它与同步双栈的本质完全相同：每个栈深度都保存当时的最小值，只是数据组织方式不同。

复杂度分析

设当前栈中有 n 个元素：

push：时间复杂度 O(1)；
pop：时间复杂度 O(1)；
top：时间复杂度 O(1)；
getMin：时间复杂度 O(1)；
空间复杂度：O(n)。

辅助栈最多保存 n + 1 个元素，常数倍额外空间不改变渐进复杂度。

边界与陷阱

每次 getMin() 遍历数据栈：会退化为 O(n)，不满足题目要求。
只用一个变量保存最小值：最小元素弹出后无法恢复上一个最小值。
两个栈没有同步弹出：栈深度不再对应，后续 getMin() 会返回过期结果。
忽略重复最小值：压缩辅助栈时必须使用 <=，不能只用 <。
直接把可变数组返回给调用方：题目只要求返回元素值，不应暴露内部栈。
额外处理题目保证不会发生的空栈操作：LeetCode 保证调用 pop、top、getMin 时栈非空；工程实现中则应根据接口约定选择抛出异常或返回特殊值。
误认为这是单调栈：同步 minStack 保存的是前缀最小值序列，它确实单调不增，但本题不涉及通过弹出候选元素解决“下一个更大/更小元素”问题。

面试官递进追问

1. 为什么只保存一个当前最小值不够？

因为当前最小值被弹出后，需要恢复它之前的最小值。单个变量没有保存历史，而辅助栈能按照后进先出的顺序恢复每一层状态。

2. 辅助栈维护的核心不变量是什么？

对于数据栈的每个深度，辅助栈对应位置保存该深度下所有数据的最小值，因此辅助栈顶始终等于数据栈当前最小值。

3. 为什么 `push` 时辅助栈也要压入一个值，即使最小值没变？

为了让两个栈的每一层一一对应。之后同步弹出时，辅助栈可以直接恢复到上一个深度的最小值，不需要判断被弹出的元素是否为最小值。

4. 为什么压缩辅助栈时要用 `<=`？

如果新元素等于当前最小值，也必须记录一次。否则弹出一个重复最小值后，会过早删除唯一的最小值记录。

5. 能否让空间复杂度降到 `O(1)`？

可以使用数值差值编码，把每个元素与当前最小值的差压入同一个栈，只额外维护一个最小值变量；但栈本身仍需 O(n) 空间，所谓 O(1) 只是辅助变量空间。差值还可能在固定宽度整数语言中溢出，工程上通常不如双栈清晰可靠。

6. 如何支持 `getMax()`？

再维护一个同步的 maxStack，其每一层保存当前最大值。所有操作仍为 O(1)，整体空间仍为 O(n)。

常见错误回答

“用栈就可以”：普通栈不能在 O(1) 时间获得全局最小值，需要说明额外状态。
“辅助栈是单调栈”：没有说清楚它保存的是每个深度的历史最小值，而不是下一个更小元素的候选。
“最小值入辅助栈，其他值不管”：需要说明重复最小值如何处理。
“空间复杂度是 O(1)”：两个栈中的元素数量都随输入增长，整体空间为 O(n)。
只验证示例中的 -3：没有检查连续弹出、重复最小值和最小值恢复。

可迁移总结

当动态数据结构需要在删除后恢复聚合值时，可以为每个历史版本保存聚合状态。
栈的后进先出顺序，天然适合保存和恢复状态历史。
同步辅助栈的通用公式是：新状态 = combine(旧状态, 新元素)。
设计数据结构时，先写出每次操作后必须成立的不变量，再让所有方法共同维护它。

刷题后自测

minStack[i] 的准确含义是什么？
连续执行 push(2)、push(1)、push(1) 后，两个栈分别是什么？
为什么两个栈同步 pop 后，可以直接恢复上一个最小值？
压缩辅助栈时，把 <= 写成 < 会在哪个示例中出错？
单栈存 { value, min } 与同步双栈的本质是否相同？

#155. 最小栈

#先给结论

#题目描述

#问题本质

#核心设计：同步辅助栈

#状态定义

#核心不变量

#逐步推演

#初始状态

#第 1 步：push(-2)

#第 2 步：push(0)

#第 3 步：push(-3)

#第 4 步：pop()

#代码实现

#JavaScript：同步双栈

#代码与思路对照

#正确性证明

#初始状态

#执行 push(val)

#执行 pop()

#重复最小值为什么容易出错

#替代方案一：辅助栈只记录最小值变化

#替代方案二：单栈存二元组

#复杂度分析

#边界与陷阱

#面试官递进追问

#1. 为什么只保存一个当前最小值不够？

#2. 辅助栈维护的核心不变量是什么？

#3. 为什么 push 时辅助栈也要压入一个值，即使最小值没变？

#4. 为什么压缩辅助栈时要用 <=？

#5. 能否让空间复杂度降到 O(1)？

#6. 如何支持 getMax()？

#常见错误回答

#可迁移总结

#刷题后自测

155. 最小栈

先给结论

题目描述

问题本质

核心设计：同步辅助栈

状态定义

核心不变量

逐步推演

初始状态

第 1 步：`push(-2)`

第 2 步：`push(0)`

第 3 步：`push(-3)`

第 4 步：`pop()`

代码实现

JavaScript：同步双栈

代码与思路对照

正确性证明

初始状态

执行 `push(val)`

执行 `pop()`

重复最小值为什么容易出错

替代方案一：辅助栈只记录最小值变化

替代方案二：单栈存二元组

复杂度分析

边界与陷阱

面试官递进追问

1. 为什么只保存一个当前最小值不够？

2. 辅助栈维护的核心不变量是什么？

3. 为什么 `push` 时辅助栈也要压入一个值，即使最小值没变？

4. 为什么压缩辅助栈时要用 `<=`？

5. 能否让空间复杂度降到 `O(1)`？

6. 如何支持 `getMax()`？

常见错误回答

可迁移总结

刷题后自测