题目描述
设计一个支持 push、pop、top 操作，并且能够在常数时间内检索到最小元素的栈。
实现 MinStack 类：
-
MinStack()初始化堆栈对象 -
void push(int val)将元素val推入堆栈 -
void pop()删除堆栈顶部的元素 -
int top()获取堆栈顶部的元素 -
int getMin()
这道题看起来是一个普通的栈题，但难点在于：如何让获取最小值的操作也保持 O(1)。
题目分析
如果只用一个普通栈来存数据，那么：
-
push是 O(1) -
pop是 O(1) -
top是 O(1) -
但是
getMin()如果每次都遍历整个栈，时间复杂度就会变成 O(n)
显然这不符合题目的要求。
所以我们需要额外设计一种结构，在每次元素变化时，同步维护当前最小值。
这也是这道题的核心思路：
用一个正常栈存所有元素，再用一个辅助栈专门维护“当前最小值”。
核心思路
代码中一共维护了两个栈：
-
stack：正常的数据栈，负责存储所有入栈元素 -
min_stack：辅助栈，负责维护当前最小值
1. 入栈操作
每次执行 push(x) 时：
-
先把
x放入正常栈stack -
如果
min_stack为空，或者x <= min_stack.peek()，就把x也压入min_stack
也就是说，辅助栈中保存的是：
-
当前最小值
-
以及历史上可能还会再次成为最小值的元素
这样设计的好处是：
-
栈顶始终就是当前最小值
-
可以直接通过
min_stack.peek()得到答案
2. 出栈操作
每次执行 pop() 时：
-
先从正常栈中弹出栈顶元素
-
如果这个元素刚好等于
min_stack的栈顶，说明当前最小值被删掉了 -
这时也要同步弹出
min_stack的栈顶
这样一来，辅助栈新的栈顶就自动变成了“剩余元素中的最小值”。
3. 获取栈顶元素
这个操作不复杂，直接返回 stack.peek() 即可。
4. 获取最小值
因为辅助栈始终维护当前最小值，所以直接返回：
min_stack.peek()
时间复杂度就是 O(1)。
为什么辅助栈可行
我们用一个例子来理解。
假设依次执行：
push(3)
push(5)
push(2)
push(2)
push(1)
那么两个栈的变化如下：
| 操作 | stack | min_stack |
|---|---|---|
| push(3) | [3] | [3] |
| push(5) | [3, 5] | [3] |
| push(2) | [3, 5, 2] | [3, 2] |
| push(2) | [3, 5, 2, 2] | [3, 2, 2] |
| push(1) | [3, 5, 2, 2, 1] | [3, 2, 2, 1] |
注意这里有一个关键点：
当压入的元素等于当前最小值时，也要放进辅助栈。
比如两个 2 都要进入 min_stack，因为后面如果弹出一个 2，另一个 2 仍然可能是最小值。
再看出栈过程：
pop() // 弹出 1
此时：
-
stack = [3, 5, 2, 2] -
min_stack = [3, 2, 2]
最小值自动变成 2。
继续：
pop() // 弹出 2
此时：
-
stack = [3, 5, 2] -
min_stack = [3, 2]
最小值仍然还是 2。
这就说明辅助栈正确维护了最小值的变化过程。
代码讲解
Java 代码
class MinStack {
private Stack<Integer> stack;
private Stack<Integer> min_stack;
public MinStack() {
stack = new Stack<>();
min_stack = new Stack<>();
}
public void push(int x) {
stack.push(x);
if (min_stack.isEmpty() || x <= min_stack.peek())
min_stack.push(x);
}
public void pop() {
if (stack.pop().equals(min_stack.peek()))
min_stack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return min_stack.peek();
}
}
代码细节分析
1. 为什么 push 里要用 <=
if (min_stack.isEmpty() || x <= min_stack.peek())
min_stack.push(x);
这里不能只写成 <。
因为如果当前最小值已经是 2，又压入了一个 2，那么这个新的 2 也必须进入辅助栈。
否则当其中一个 2 被弹出时，辅助栈会错误地失去这个最小值记录。
所以必须保留重复最小值。
2. 为什么 pop 要比较是否等于当前最小值
if (stack.pop().equals(min_stack.peek()))
min_stack.pop();
正常栈弹出一个元素后，只有当这个元素恰好就是当前最小值时，辅助栈才需要同步弹出。
如果弹出的不是最小值，那么 min_stack 不需要变化。
3. 为什么这里用 equals() 而不是 ==
stack.pop().equals(min_stack.peek())
因为 stack.pop() 和 min_stack.peek() 返回的都是 Integer 对象。
-
==比较的是对象地址 -
equals()比较的是数值是否相等
在这里显然应该比较数值，所以使用 equals() 更稳妥。
示例推演
假设执行以下操作：
push(-2)
push(0)
push(-3)
getMin()
pop()
top()
getMin()
执行过程如下：
第一步：push(-2)
-
stack = [-2] -
min_stack = [-2]
第二步：push(0)
-
stack = [-2, 0] -
min_stack = [-2]
因为 0 不是更小的值，所以辅助栈不变。
第三步：push(-3)
-
stack = [-2, 0, -3] -
min_stack = [-2, -3]
因为 -3 比当前最小值 -2 更小，所以也进入辅助栈。
第四步：getMin()
返回 -3
第五步：pop()
弹出 -3
-
stack = [-2, 0] -
min_stack = [-2]
第六步：top()
返回 0
第七步：getMin()
返回 -2
整个过程都没有遍历栈，因此每个操作都非常高效。
复杂度分析
时间复杂度
-
push：O(1) -
pop：O(1) -
top：O(1) -
getMin：O(1)
空间复杂度
-
O(n)
最坏情况下，如果每次入栈的元素都比前一个更小，那么所有元素都会进入 min_stack。
这种做法的优点
这套方法的优点非常明显：
-
思路直观，容易理解
-
所有操作都能做到 O(1)
-
非常适合这类“额外维护某种状态”的栈题
这也是这道题最经典、最常见的解法。
总结
这道题表面上是在考栈，实际上真正考察的是：
如何在原有数据结构的基础上，用额外空间维护一个动态变化的信息。
本题中，这个“额外信息”就是当前最小值。
所以我们的做法就是：
-
用
stack保存所有元素 -
用
min_stack保存每个阶段可能成为最小值的元素
这样一来：
-
push时同步维护最小值 -
pop时同步删除失效最小值 -
getMin时直接返回辅助栈栈顶
最终把四个操作都控制在 O(1) 时间内完成。
如果把这道题吃透，后面再遇到：
-
单调栈
-
设计栈/队列
-
维护区间最值
-
双栈实现特殊功能
这些题都会更容易理解。
