LeetCode 155. 最小栈
目录
题目描述
✅ 155. 最小栈
题意分析
这是一道数据结构设计题：实现一个栈，除了常规的
push、pop、top，还要能在常数时间内返回栈内的最小元素。题面对getMin的常数时间要求是明写的，这条要求就是全部难点所在。关键要看清
getMin的语义：它求的是当前栈里所有元素的最小值，会随着pop回退到历史取值。所以它不是「历史上出现过的最小值」，一个只增不减的min变量无法表达它。「栈」这个容器本身透露了最重要的算法信号：删除总是发生在最新插入的那一端。这意味着栈的内容完全由「当前深度」决定——深度为
d时栈里就是最早压入的那d个元素，绝不会出现「中间某个元素被抽走」的情况。这条先验信息使得任何「只依赖当前栈内容」的派生量都能被逐层记录下来并随着pop精确回退。题面保证
pop、top、getMin只在栈非空时调用，因此不需要为空栈设计返回值或抛异常；但push的第一次调用要处理辅助结构为空的情形。元素允许重复（可能有多个相同的最小值），取值也可以是负数，因此不能拿
0或某个特殊数当哨兵。
解法：主栈 + 同步最小栈
核心思路
主栈保存元素，辅助栈与主栈等高；辅助栈每一层保存主栈在对应深度时的最小值。入栈时把
min(val, 当前最小值)同步压入辅助栈，出栈时两个栈同步弹出，因此getMin只需读取辅助栈顶。
解题步骤
- 初始化主栈
stack和辅助栈minStack。push：主栈压入元素，辅助栈压入当前层的最小值。pop：两个栈同时弹出栈顶，恢复到上一层状态。top返回主栈顶，getMin返回辅助栈顶。
代码实现
class MinStack {
private final Deque<Integer> stack = new ArrayDeque<>();
private final Deque<Integer> minStack = new ArrayDeque<>();
public MinStack() {
}
public void push(int val) {
stack.push(val);
minStack.push(minStack.isEmpty() ? val : Math.min(val, minStack.peek()));
}
public void pop() {
stack.pop();
minStack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
type MinStack struct {
stack []int
minStack []int
}
func Constructor() MinStack {
return MinStack{}
}
func (s *MinStack) Push(val int) {
minimum := val
if len(s.minStack) > 0 && s.minStack[len(s.minStack)-1] < minimum {
minimum = s.minStack[len(s.minStack)-1]
}
s.stack = append(s.stack, val)
s.minStack = append(s.minStack, minimum)
}
func (s *MinStack) Pop() {
s.stack = s.stack[:len(s.stack)-1]
s.minStack = s.minStack[:len(s.minStack)-1]
}
func (s *MinStack) Top() int {
return s.stack[len(s.stack)-1]
}
func (s *MinStack) GetMin() int {
return s.minStack[len(s.minStack)-1]
}
复杂度分析
- 时间复杂度：四个操作均为 $O(1)$；动态数组扩容时，
push为摊还 $O(1)$。- 空间复杂度：$O(n)$，两个栈各保存至多
n个元素。
关键点总结
- 辅助栈顶始终是当前主栈的最小值。
- 每次入栈都记录最小值，重复最小值也能正确回退。
- 两个栈必须始终保持相同高度。
易错点总结
- 只维护一个最小值变量，弹出最小元素后无法恢复上一个最小值。
pop时只弹主栈，会让两个栈的状态错位。- 辅助栈首次入栈时没有旧最小值，应直接压入
val。top读取主栈，getMin才读取辅助栈。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 225. 用队列实现栈 | 简单 | 反方向模拟：用先进先出的容器造后进先出，考的是操作转换而不是附加信息维护 |
| 232. 用栈实现队列 | 简单 | 双栈倒腾实现先进先出，pop 只有摊还 $O(1)$，是练摊还分析的入门题 |
| 239. 滑动窗口最大值 | 困难 | 删除发生在与插入相反的一端，历史不能整体回退，辅助栈失效，必须换成单调双端队列 |
| 716. 最大栈 | 困难 | 除了常数时间取最大值还要支持 popMax，会破坏栈序，等高辅助栈不够用 |
| 895. 最大频率栈 | 困难 | 待查询的量是「频率最高且最靠栈顶」，要按频率分层建多个栈，而不是逐层记一个结论 |
| 1381. 设计一个支持增量操作的栈 | 中等 | 需要对栈底若干元素批量加值，靠「延迟增量数组」把批量修改摊到出栈时逐个结算 |
| 剑指 Offer 30. 包含min函数的栈 | 简单 | 与本题同题换皮，适合用来检验不变量能否脱稿讲清 |
| 面试题 03.02. 栈的最小值 | 简单 | 同样的结构，但方法命名与空栈行为的约定略有不同，注意按各自题面的保证来决定要不要兜底 |