LeetCode 剑指 Offer 31. 栈的压入、弹出序列
题目描述
题意分析
给定一批互不相同元素的压栈顺序，以及它们的目标弹栈顺序，判断是否能通过合法栈操作实现。压栈必须遵循第一条序列，弹栈必须遵循第二条序列，但压入和弹出可以交错进行。
栈只能从顶部取元素，不能跳过栈顶去取更下面的目标。需要判断目标顺序是否可实现，不是先把所有元素压完，再检查它们是否恰好逆序。
解法：辅助栈模拟
核心思路
[!blue]
用辅助栈模拟已压入但还未弹出的元素，用
j指向目标弹出序列中下一个必须出现的值。按给定顺序压入元素之后，只要栈顶等于popped[j]，就立即弹出并推进j，直到下一目标不在栈顶。立即弹出为什么不会错过合法方案？当下一目标已经在栈顶时，继续压入别的元素会把它盖住；新元素若想被移开，就必须抢在当前目标前弹出，这与指定顺序冲突。元素互不相同，因此也不能等待未来另一个同值元素替代它，此时弹出是被目标顺序确定的动作。
如果栈顶不是下一目标，当前栈顶不能先弹出，只能继续按顺序压入剩余元素，等待目标到达顶部。一次新压入可能触发多次连续弹出，露出更深的后续目标，所以匹配过程必须使用循环。
所有元素压入完成后，若
j已走到目标末尾，说明每次弹出都与目标一致，实现成功；若还有目标没有消费，此时没有新元素可压入，也不能按目标顺序弹出栈顶，便无法完成。
解题步骤
- 创建空辅助栈，令
j = 0，表示尚未匹配任何弹出元素。- 按
pushed顺序压入当前值。- 当栈非空、目标尚未全部匹配且栈顶等于
popped[j]时，弹出栈顶并令j++，继续检查。- 完成一次连续匹配后，继续压入下一个元素。
- 全部压入结束，返回
j == popped.length；两条序列都为空时也自然匹配完成。
代码实现
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
Deque<Integer> stack = new ArrayDeque<>();
int j = 0;
for (int value : pushed) {
stack.push(value);
// 当前目标在栈顶就立即弹出，可能连续匹配多个目标。
while (!stack.isEmpty() && j < popped.length && stack.peek() == popped[j]) {
stack.pop();
j++;
}
}
return j == popped.length;
}
}
func validateStackSequences(pushed []int, popped []int) bool {
stack := make([]int, 0, len(pushed))
j := 0
for _, value := range pushed {
stack = append(stack, value)
// 当前目标在栈顶就立即弹出，可能连续匹配多个目标。
for len(stack) > 0 &&
j < len(popped) &&
stack[len(stack)-1] == popped[j] {
stack = stack[:len(stack)-1]
j++
}
}
return j == len(popped)
}
复杂度分析
- 时间复杂度：$O(n)$，每个元素恰好压栈一次，至多弹出一次，内层匹配循环的总次数不超过
n。- 空间复杂度：$O(n)$，目标迟迟不在栈顶时，辅助栈可能先保存全部元素。
关键点总结
[!green]
- 栈表示已压未弹部分，
j表示已经正确完成的弹出数量，两者共同描述模拟进度。- 目标在栈顶时立即弹出，目标不在栈顶时只能继续压入，不需要搜索所有操作顺序。
- 压入和弹出需要交错，一次压入也可能引发多次弹出。
- 只有全部目标被依次消费，才能判断整个弹出序列合法。
易错点总结
[!yellow]
- 每次压入后只用一次
if，会漏掉连续弹出多个已在栈中的目标。- 将所有元素先压入再开始比较，把题目允许的交错操作错误限制成一次性倒序。
- 在读取栈顶或
popped[j]前没有检查范围，连续弹出结束时可能越界。- 弹出后忘记推进
j，下一次仍拿旧目标比较，破坏匹配进度。- 从容器尾部加入却从头部读取，实际上模拟成队列，必须让压入、取顶和弹出使用同一端。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 20. 有效的括号 | 简单 | 同样用栈模拟合法出入顺序，本题按给定压入序列推进，直到能匹配下一待弹值。 |
| 补充题 133. 字典序最大的出栈序列 | 中等 | 原题在所有合法出栈序列中求字典序最大，本题只验证某个给定序列是否可实现。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！