LeetCode 155中等栈 · 辅助栈
最小栈 图解题解
普通栈查最小值要从头翻，有办法让 getMin 也做到 O(1) 吗？再加一个辅助栈就够了。
像同时维护两本账：主账本记所有数字的进出；副账本只记「每一时刻的最小值」——每压入一个更小（或相等）的数，就在副账本也同步记一条。弹出时，若弹掉的正好是副账本顶端，副账本也跟着弹。于是任何时候翻开副账本顶端，瞬间得到当前最小值，不用重新扫主账本。
这道题到底在问什么
设计一个支持 push、pop、top，并能 O(1) 获取最小元素的栈。
- 操作
- push(-2), push(0), push(-3), getMin(), pop(), getMin()
- 输出
- -3, -2
最优解：一步一步想明白
- 3如果每次查询最小值都遍历整个栈，设计题就失去意义。
- 4当新值小于等于当前最小值，就同步压入辅助栈。等号不能丢：重复最小值要各存一份。
- 5push-2 是第一个元素，也是当前最小值。两个栈都压入 -2。
- 6push0 大于当前最小 -2，只进数据栈，最小栈不动。
- 7new min-3 更小，同步进入最小栈。现在 getMin 是 -3。
- 8弹的值 == 最小栈顶 → 两栈同步弹 → getMin 免费恢复上一个最小这就是最小栈的灵魂。刚才弹出的 -3 正好等于最小栈顶，所以最小栈也跟着弹一个。瞬间，getMin 自动回到上一个最小值 -2——没有重新扫描，因为「每一刻的最小值」早就一层层存在最小栈里了。最小值有历史，就能跟着数据栈一起进退。
- 9新示例 push(-2), push(-2)：相等也要入最小栈单独看一个小例子：连续压入两个 -2。两个都是最小值，第二个 -2 也必须进最小栈——所以入栈判断要用「小于等于」而不是「小于」。这样以后弹掉一个 -2，getMin 仍能看到另一个 -2。
- 10回到刚才 [-2, 0] 那个栈。查询最小值时只读最小栈的栈顶，一步就拿到 -2，所以 getMin 是 O(1)，完全不用扫描数据栈。
- 13辅助栈顶永远代表当前数据栈的最小值。
- 16use ≤两个 -2 都是最小值。如果第二个 -2 没进最小栈，弹掉一个后 getMin 就会出错。
- 21这题学完不要乱跳，下一步去 对应专题 连刷同类题；卡住时用 AI 答疑追问“为什么这一步成立”，比只背答案更稳。
⚠️ 容易写错的地方
✗ 错：push 时只在 val < min 才入最小栈
✓ 对：重复最小值也要入最小栈：小于等于当前最小值
否则弹出一个最小值后，辅助栈会提前丢掉仍然存在的最小值。
✗ 错：pop 时不维护最小栈
✓ 对：弹出的值等于 min 栈顶时同步弹
否则最小值会过期。
✗ 错：getMin 扫数据栈
✓ 对：直接返回 min 栈顶
设计目标要求 O(1)。
完整代码（Python / C++ / Java）
Python
class MinStack:
def __init__(self):
self.st = []
self.mn = []
def push(self, val):
self.st.append(val)
if not self.mn or val <= self.mn[-1]:
self.mn.append(val)
def pop(self):
x = self.st.pop()
if x == self.mn[-1]:
self.mn.pop()
def top(self):
return self.st[-1]
def getMin(self):
return self.mn[-1]C++
class MinStack {
stack<int> st, mn;
public:
void push(int val) {
st.push(val);
if (mn.empty() || val <= mn.top()) mn.push(val);
}
void pop() {
int x = st.top(); st.pop();
if (x == mn.top()) mn.pop();
}
int top() { return st.top(); }
int getMin() { return mn.top(); }
};Java
class MinStack {
Deque<Integer> st = new ArrayDeque<>();
Deque<Integer> mn = new ArrayDeque<>();
public void push(int val) {
st.push(val);
if (mn.isEmpty() || val <= mn.peek()) mn.push(val);
}
public void pop() {
int x = st.pop();
if (x == mn.peek()) mn.pop();
}
public int top() { return st.peek(); }
public int getMin() { return mn.peek(); }
}套路模板 · 最小栈专属骨架
class MinStack:
def __init__(self):
self.data = []
self.mins = []
def push(self, val):
self.data.append(val)
if not self.mins or val <= self.mins[-1]:
self.mins.append(val)
def pop(self):
x = self.data.pop()
if x == self.mins[-1]: self.mins.pop()
def top(self): return self.data[-1]
def getMin(self): return self.mins[-1]class MinStack {
vector<int> data, mins;
public:
void push(int val) {
data.push_back(val);
if (mins.empty() || val <= mins.back()) mins.push_back(val);
}
void pop() {
int x = data.back(); data.pop_back();
if (x == mins.back()) mins.pop_back();
}
int top() { return data.back(); }
int getMin() { return mins.back(); }
};class MinStack {
Deque<Integer> data = new ArrayDeque<>();
Deque<Integer> mins = new ArrayDeque<>();
public void push(int val) {
data.push(val);
if (mins.isEmpty() || val <= mins.peek()) mins.push(val);
}
public void pop() {
int x = data.pop();
if (x == mins.peek()) mins.pop();
}
public int top() { return data.peek(); }
public int getMin() { return mins.peek(); }
}复杂度
push/pop/top/getMin
O(1)
每个操作只碰栈顶
空间复杂度
O(n)
最坏每个元素都进入最小栈
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 最小栈 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
能只用一个栈吗？+
可以：栈里存 pair(值, 当前最小)，每个节点自带「压到这一层时的最小值」，pop 时一起出栈。
辅助栈最坏为什么是 O(n) 空间？+
若元素一直递减，每个都会刷新最小值、都得进辅助栈，辅助栈和数据栈一样长。
pop 空栈要处理吗？+
LeetCode 调用通常保证合法；工程里要么抛异常、要么返回约定的空值。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。