LC946. 验证栈序列

LC946. 验证栈序列 预习和复习可以查看我的讲解视频。

题目描述

给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回false 。 示例 1： 输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1] 输出：true 解释：我们可以按以下顺序执行： push(1), push(2), push(3), push(4), pop() -> 4, push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1 示例 2： 输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2] 输出：false 解释：1 不能在 2 之前弹出。 提示： 1 <= pushed.length <= 1000 0 <= pushed[i] <= 1000 pushed 的所有元素 互不相同 popped.length == pushed.length popped 是 pushed 的一个排列

题目解析

解题思路

本题的核心是模拟栈的入栈和出栈过程，验证给定的 popped 序列是否可能由 pushed 序列的入栈顺序通过合法出栈得到。

由于所有元素互不相同，我们只需用一个真实的栈来模拟。遍历 pushed 数组，依次将元素压入栈中；每次压入后，检查栈顶元素是否等于 popped 当前指向的元素，若相等则弹出栈顶，并将 popped 的指针后移。重复此过程直到栈顶不再匹配。最后，若栈为空，说明所有元素都能按 popped 顺序合法弹出，返回 true；否则返回 false。

关键步骤

1. 初始化：一个空列表 stack 模拟栈，一个指针 index 指向 popped 的当前待匹配位置（初始为 0）。 2. 遍历 pushed：对每个元素执行 stack.append(pushed[i])。 3. 循环检查栈顶：当栈非空且栈顶元素等于 popped[index] 时，执行 stack.pop() 并 index += 1，直到条件不满足。 4. 最终判定：遍历结束后，若 stack 为空则返回 True，否则返回 False。

示意图（以示例1为例）：

pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
操作过程：
push 1 → stack=[1]
push 2 → stack=[1,2]
push 3 → stack=[1,2,3]
push 4 → stack=[1,2,3,4] → 栈顶=4=popped[0] → pop → stack=[1,2,3], index=1
push 5 → stack=[1,2,3,5] → 栈顶=5=popped[1] → pop → stack=[1,2,3], index=2
继续检查栈顶=3=popped[2] → pop → stack=[1,2], index=3
栈顶=2=popped[3] → pop → stack=[1], index=4
栈顶=1=popped[4] → pop → stack=[], index=5
最终栈空 → True

复杂度分析

• 时间复杂度：O(n)，其中 n 为 pushed 的长度。每个元素最多入栈一次、出栈一次，while 循环的总执行次数不超过 n。
• 空间复杂度：O(n)，最坏情况下栈中存储所有元素（例如 popped 为逆序时）。