LeetCode 946中等栈
验证栈序列 图解题解
这道题到底在问什么
pushed 是入栈顺序（必须按这个顺序压），popped 是期望的出栈顺序。判断 popped 是否可能是合法的弹出序列。
- 输入
- pushed=[1,2,3,4,5,6,7,8,9] popped=[3,2,4,6,5,9,8,7,1]
- 输出
- true
最优解：一步一步想明白
- 3记住这条贪心：能弹就立刻弹。下面每一帧都在套它。
- 4pushed=[1,2,3,4,5,6,7,8,9]，要按这个顺序压栈；popped=[3,2,4,6,5,9,8,7,1] 是期望的弹出顺序。从左边第一个开始压。
- 5压入 1，栈顶现在是 1。看它等不等于下一个该弹的 3。
- 6压入 2，栈顶现在是 2。看它等不等于下一个该弹的 3。
- 7压入 3，栈顶现在是 3。看它等不等于下一个该弹的 3。
- 8栈顶 3 == 该弹的 3，弹出！下一个该弹 2，当前栈顶 2。
- 9栈顶 2 == 该弹的 2，弹出！下一个该弹 4，当前栈顶 1。
- 10压入 4，栈顶现在是 4。看它等不等于下一个该弹的 4。
- 11栈顶 4 == 该弹的 4，弹出！下一个该弹 6，当前栈顶 1。
- 12压入 5，栈顶现在是 5。看它等不等于下一个该弹的 6。
- 13压入 6，栈顶现在是 6。看它等不等于下一个该弹的 6。
- 14栈顶 6 == 该弹的 6，弹出！下一个该弹 5，当前栈顶 5。
- 15栈顶 5 == 该弹的 5，弹出！下一个该弹 9，当前栈顶 1。
- 16压入 7，栈顶现在是 7。看它等不等于下一个该弹的 9。
- 17压入 8，栈顶现在是 8。看它等不等于下一个该弹的 9。
- 18压入 9，栈顶现在是 9。看它等不等于下一个该弹的 9。
- 19栈顶 9 == 该弹的 9，弹出！下一个该弹 8，当前栈顶 8。
- 20栈顶 8 == 该弹的 8，弹出！下一个该弹 7，当前栈顶 7。
- 21栈顶 7 == 该弹的 7，弹出！下一个该弹 1，当前栈顶 1。
- 22栈顶 1 == 该弹的 1，弹出！弹出序列走完，栈已空。
- 23全部压完、栈正好空、popped 全弹出 ⇒ 这是一个合法的弹出序列，返回 true。（若结束时栈非空，则返回 false）
⚠️ 容易写错的地方
✗ 错：压完不检查就继续
✓ 对：每压一个都 while 连弹
该弹的可能连着好几个，漏弹会判错
✗ 错：忘了 j 越界判断
✓ 对：while 里加 j < len(popped)
popped 弹完后 popped[j] 会越界
✗ 错：结束不看栈空
✓ 对：最后 return 栈是否为空
压完还剩元素说明弹不出该顺序
完整代码（Python / C++ / Java）
Python
def validateStackSequences(pushed, popped):
st, j = [], 0
for x in pushed:
st.append(x)
while st and j < len(popped) and st[-1] == popped[j]:
st.pop(); j += 1
return not stC++
bool validateStackSequences(vector<int>& pushed, vector<int>& popped){
stack<int> st; int j = 0;
for(int x : pushed){
st.push(x);
while(!st.empty() && j < popped.size() && st.top() == popped[j]){
st.pop(); j++;
}
}
return st.empty();
}Java
public boolean validateStackSequences(int[] pushed, int[] popped){
Deque<Integer> st = new ArrayDeque<>();
int j = 0;
for(int x : pushed){
st.push(x);
while(!st.isEmpty() && j < popped.length && st.peek() == popped[j]){
st.pop(); j++;
}
}
return st.isEmpty();
}复杂度
时间
O(n)
每个元素至多压一次、弹一次
空间
O(n)
模拟栈最多装下全部元素
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 验证栈序列 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
怎么证明这个贪心是对的？+
某元素一旦能弹（栈顶 == 当前要弹的）就必须立刻弹：再压新元素只会把它埋更深，之后更弹不出来。所以「能弹就弹」不会错过任何合法解。
如果 pushed 和 popped 元素不是同一组数怎么办？+
题目保证两者是同一组数的排列；若不保证，可先判两数组是否互为排列，不是则直接 false。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 验证栈序列 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。