#155
简单
中频
栈最小栈
这是一道围绕栈展开的高频练习。建议先掌握「栈」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。
栈
题目分析
这道题表面上是在处理「最小栈」，但先要想清楚题目到底让你返回什么，以及过程中哪些约束必须一直满足。从题型上看，它主要在考 栈 这些能力。这类题的重点往往不是代码量，而是识别“后进先出”的顺序是否正好对应题目的处理需求。只有先把题目要求翻译成人话，后面的推荐代码才是在实现思路，而不是直接给答案。
接下来怎么看推荐代码： 带着这个理解再看推荐代码时，重点观察这条主线：主栈存正常元素，辅助最小栈同步维护到当前位置为止的最小值。
推荐代码
推荐解法：栈
时间复杂度： O(1)
空间复杂度： O(n)
核心思路： 主栈存正常元素，辅助最小栈同步维护到当前位置为止的最小值。
class MinStack {
Deque<Integer> xStack;
Deque<Integer> minStack;
public MinStack() {
xStack = new LinkedList<Integer>();
minStack = new LinkedList<Integer>();
minStack.push(Integer.MAX_VALUE);
}
public void push(int x) {
xStack.push(x);
minStack.push(Math.min(minStack.peek(), x));
}
public void pop() {
xStack.pop();
minStack.pop();
}
public int top() {
return xStack.peek();
}
public int getMin() {
return minStack.peek();
}
}结构化讲解
面试时怎么讲
开场思路
这题我会用双栈：一个正常存值，一个同步存当前最小值。
核心过程
- push 时两个栈一起入栈。
- 辅助栈压入的是“截至当前的最小值”。
- pop 时两个栈一起弹出保持深度一致。
- 因此 getMin 只要看辅助栈顶即可。
复杂度总结
所有操作时间复杂度都为 O(1)，空间复杂度 O(n)。
面试补一句：这题最核心的设计不是两个栈，而是“最小值和栈深同步”。
核心思路
最小栈的难点在于既要像普通栈那样 push/pop，又要随时 O(1) 拿到最小值。解决方式是让最小值也跟着栈深同步存下来。
步骤讲解
1
入栈时同步更新最小栈
压入新元素时，同时把“当前最小值”压入辅助栈。
为什么这样做：这样每个栈深位置都知道当时的最小值。
对应代码提示：minStack.push(Math.min(val, minStack.peek()));
2
出栈时两个栈同步弹出
主栈弹出一个元素时，最小栈也一起弹出。
为什么这样做：两者必须保持同样深度，最小值才和当前位置对应。
对应代码提示：stack.pop(); minStack.pop();
3
取最小值直接看最小栈栈顶
当前栈对应的最小值始终保存在辅助栈顶。
为什么这样做：辅助栈已经把所有历史最小值同步记录好了。
对应代码提示：return minStack.peek();
易错点
只在值更小时才压最小栈
会让两个栈深度不同，pop 后无法正确恢复上一个最小值。
正确理解：每次 push 都要让最小栈也同步 push。
把最小值现算一遍
那会把 getMin 退化成 O(n)。
正确理解：最小值必须在入栈时就维护好。
最小栈空时没处理首元素
首个元素入栈时无法比较前一个最小值。
正确理解：首个元素直接同时压入两个栈。
复杂度与适用判断
时间复杂度：O(1)
空间复杂度：O(n)
比其他方案更好在哪里：比每次扫描求最小值高效很多，完全满足题目 O(1) 要求。
适用判断：数据结构设计题若要求在原操作外额外维护聚合信息，常见思路就是“同步栈/同步状态”。
额外提醒
- 辅助栈存的不是历史最小值集合，而是每一层对应的当前最小值。
动画演示
如果你还没完全看懂，可以展开动画演示。
栈动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
栈动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
支持的操作: push(value), pop(), top(), getMin()
准备就绪 - 输入栈操作序列，然后点击开始
动画演示仅在桌面端提供，移动端请优先阅读推荐代码与结构化讲解。