LeetCode 946. 验证栈序列
题目描述
题意分析
pushed规定元素进入栈的先后顺序，popped规定希望看到的出栈顺序。可以在入栈之间穿插出栈，但每次只能弹出栈顶，不能越过它取走下面的元素。题目保证两个数组等长、元素互不重复，且包含相同的元素。因此需要判断的是顺序能否实现，而不是元素是否相同。用
j指向下一个必须弹出的popped[j]。
解法：栈模拟入栈出栈
核心思路
[!blue]
直接按
pushed的顺序模拟入栈。栈里保存“已经入栈、尚未按目标顺序弹出”的元素；popped[0..j-1]则是已经成功匹配的出栈前缀。若栈顶等于
popped[j]，就应立即弹出它：继续压入其他元素会把当前目标盖住，而上面的元素又不能先于当前目标出栈。因而立刻弹出不会排除任何合法方案。弹出后，新栈顶可能又是下一个目标，所以要一直弹到不匹配为止。若栈顶不等于下一个目标，此时不能弹出任何元素，只能尝试继续入栈。算法始终只执行符合目标的弹出动作，也不会跳过一个可以完成的弹出动作。全部元素压入后，若仍有目标未匹配，既没有新的元素可压入，栈顶也无法匹配，便不存在合法方案。
解题步骤
- 创建空栈，令
j = 0，表示尚未匹配任何出栈元素。- 按
pushed的顺序将当前元素压栈。- 只要栈非空、
j尚未到末尾且栈顶等于popped[j]，就弹出栈顶并递增j，随后检查新栈顶。- 当前栈顶不能继续匹配时，回到入栈流程。所有入栈元素处理完后，返回
j == popped.length。由于两个数组等长，
j到达末尾也意味着所有入栈元素都已弹出，栈必然为空；无需再增加另一套成功条件。
代码实现
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)
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$ 为序列长度。每个元素入栈一次、最多出栈一次，内层循环的总执行次数不超过 $n$。
- 空间复杂度：$O(n)$。若首个出栈目标是最后入栈的元素，模拟栈会暂时保存全部元素。
关键点总结
[!green]
- 栈记录尚未弹出的元素，
j记录已经匹配了多少个目标，两者共同描述模拟状态。- 下一个目标就在栈顶时必须先弹出；栈顶不符时不能随意弹出，只能继续入栈。
- 最后检查目标是否全部匹配，便同时验证了出栈顺序和全部元素的消费。
易错点总结
[!yellow]
- 用
if代替while：一次只弹一个元素，会漏掉连续可弹出的栈顶。- 不检查栈是否为空就读取栈顶：合法序列清空栈后会发生异常。
- 栈顶暂时不匹配就返回
false：此时仍可能通过继续入栈得到目标元素。- 只判断两个数组互为排列：这是题目已经保证的条件，仍需验证后进先出的顺序约束。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 20. 有效的括号 | 简单 | 同样用栈模拟合法出入顺序，本题按给定压入序列推进，直到能匹配下一待弹值。 |
| 补充题 133. 字典序最大的出栈序列 | 中等 | 原题在所有合法出栈序列中求字典序最大，本题只验证某个给定序列是否可实现。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！