0155. Min Stack¶
题目信息¶
- 题号:
最小栈
- 难度:
Medium
- 主题:
栈、设计、前缀最小值、同步状态
- 原题:
- 重点:
为每个栈深度保留当时的最小值,使弹栈能直接恢复历史状态,并正确处理重复最小值
题目重述¶
设计 MinStack,支持 push(val)、pop()、top()、getMin()。前两者遵守普通栈的后进先出;
top 返回栈顶值,getMin 返回当前栈内最小值。四种操作都必须为 O(1)。测试保证在非空栈上调用
pop、top 和 getMin。
自建示例¶
push(5), push(2), push(2), push(7)
getMin() -> 2
pop() 删除 7
pop() 删除一个 2
getMin() -> 2 另一个 2 仍在栈中
执行 push(-4), push(9) 后,top() 返回 9,getMin() 返回 -4;栈顶与全栈最小值是两种
不同状态。
C++ 实现¶
#include <algorithm>
#include <stack>
#include <utility>
class MinStackWithTwoStacks {
private:
std::stack<int> values_;
std::stack<int> minimums_;
public:
void push(int value) {
values_.push(value);
if (minimums_.empty() || value <= minimums_.top()) {
minimums_.push(value);
}
}
void pop() {
if (values_.top() == minimums_.top()) {
minimums_.pop();
}
values_.pop();
}
int top() {
return values_.top();
}
int getMin() {
return minimums_.top();
}
};
class MinStack {
private:
std::stack<std::pair<int, int>> entries_;
public:
MinStack() = default;
void push(int value) {
const int minimumAfterPush = entries_.empty()
? value
: std::min(value, entries_.top().second);
entries_.push({value, minimumAfterPush});
}
void pop() {
entries_.pop();
}
int top() {
return entries_.top().first;
}
int getMin() {
return entries_.top().second;
}
};
题解¶
为什么只保存当前最小值仍然不够¶
普通栈只需保存元素,push、pop、top 都访问一端。若 getMin 每次扫描全栈,最坏为 O(n);
若只额外保存一个变量 currentMinimum,压入时可以常数更新,但弹出当前最小元素后,不知道它下面历史
元素的最小值,仍要重新扫描。
缺少的信息不是“现在最小值是多少”,而是“回到每个旧栈深度时最小值应恢复成什么”。栈的后进先出顺序 允许把这段历史也按栈保存。
方案一:第二个栈只记录最小值变化¶
MinStackWithTwoStacks 的 values_ 保存全部值,minimums_ 保存仍有效的最小值候选。压入值不大于
当前最小时,它成为新深度的最小值并同步压入;弹出值等于当前最小时,也同步弹出最小栈。于是
minimums_.top() 始终是全栈最小值。
条件必须是 value <= minimums_.top(),不能只在严格更小时记录。连续压入两个 2 后,最小栈也应
保存两个 2;弹出上面一个时,只删除一份,下面的 2 仍证明当前最小值为二。若只记录一次,第一次
弹出就会错误暴露更大的旧最小值,甚至让最小栈为空。
该方法只在最小值不增时追加辅助项,某些输入可少存状态;代价是 push、pop 都要保持两个栈同步,
相等分支是容易出错的地方。
方案二:每一层绑定压入后的前缀最小值¶
主实现让每个栈项保存二元组:
{当前 value, 压入它之后整个栈的 minimum}
压入时,新最小值只可能是当前值或旧栈顶保存的最小值,两者取小即可。弹出时,值与这一层的最小状态一起 删除;新的栈顶已经携带上一深度的正确最小值,无需判断刚删的值是否等于最小值。
不变量与具体走读¶
entries_ 中任一位置 i 的 second,等于从栈底到位置 i 所有 first 的最小值。因此栈顶
二元组同时回答普通栈顶和全栈最小值。
操作 |
新压入二元组 |
栈顶最小值 |
|---|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
删除 |
下一项仍为 |
每次压入后不变量由 min(value, oldMinimum) 成立;弹出只恢复一个此前已经正确的前缀状态,所以归纳地
覆盖任意操作序列。
为什么不使用最小堆¶
最小堆能常数取得最小值,但删除的必须是栈顶最近元素,而它可能位于堆中间;需要额外身份、延迟删除或索引
维护,操作也通常达到 O(log n)。这里查询只随栈深度回退,前缀最小值正好匹配后进先出的历史结构,
无需引入更通用的数据结构。
主解选择与复杂度¶
公开类 MinStack 采用二元组栈。四个操作都只读取或修改栈顶,严格 O(1);每个输入元素多保存一个
整数,空间 O(n)。双栈方案同样满足时间要求,并可能在最小值很少变化时少存辅助项;二元组方案选择
固定的一层一状态对应,牺牲少量常数空间换取无分支的弹出与更容易维护的不变量。