LeetCode-Book 笔面试精选LeetCode 946「验证栈序列」的模拟栈解法与三语言实现【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book本文基于《图解算法数据结构》配套的笔面试精选 88 题中的第 946 题讲解如何借助辅助栈模拟压入/弹出操作来判定一个弹出序列是否合法。读完本文你将掌握模拟法在栈类问题中的通用套路——把题目描述的操作过程翻译成可执行代码用能否模拟成功直接回答是否可行并能在 Python、Java、C 三种语言下完整落地该算法。问题描述LeetCode 946「验证栈序列」Validate Stack Sequences给定两个整数数组pushed和popped其中popped是pushed的一个排列。如果这两个序列可以对应一系列合法的栈操作先按pushed顺序入栈再任意时刻允许出栈而得到返回true否则返回false。例如pushed [1, 2, 3, 4, 5]、popped [4, 5, 3, 2, 1]是合法的依次压入 1、2、3、4弹出 4再压入 5弹出 5、3、2、1而popped [4, 3, 5, 1, 2]则不合法因为 4 先弹出后栈顶是 33 必须在 1、2 之前弹出无法先弹出 5 再回头弹出 1。仓库中该题的完整讲解见 946. 验证栈序列。核心观察操作顺序由两个序列唯一确定本题最关键的观察是给定压入序列pushed和弹出序列popped压入/弹出操作的具体顺序排列是唯一确定的。原因在于栈的先入后出特性决定了约束压入顺序被pushed固定出栈顺序被popped固定在某一时刻只有下一个待压入的元素和当前栈顶元素两种出栈候选后者仅当栈非空。若popped的当前目标既不是下一个待压入元素、也不是栈顶则说明无论怎么操作都无法凑出这个弹出序列。反过来由于题目规定栈中所有数字均不相等每个元素出栈的位置是唯一的若存在重复数字同一值可能有多个可出栈的位置模拟法需要额外的去重处理。因此在模拟过程中一旦发现栈顶元素等于popped的当前元素就应当立即出栈不需要犹豫。模拟法算法流程借用一个辅助栈stack来模拟压入/弹出操作的排列根据能否模拟成功即可得到判定结果入栈操作严格按pushed的顺序执行出栈操作每次入栈后循环判断栈顶元素 popped[i]是否成立将符合弹出顺序的栈顶元素全部弹出。具体算法流程初始化辅助栈stack弹出序列的索引i遍历压栈序列各元素记为num元素num入栈循环出栈若stack的栈顶元素等于popped[i]则执行出栈并使i 1返回值若最终stack为空说明弹出序列合法。逐步走查一个合法示例以pushed [1, 2, 3, 4, 5]、popped [4, 5, 3, 2, 1]为例这也是仓库中 Python 代码自带的测试用例步骤操作辅助栈左→右底→顶i1压入 1[1]02压入 2[1, 2]03压入 3[1, 2, 3]04压入 44 popped[0]弹出[1, 2, 3]15压入 55 popped[1]弹出3 popped[2]弹出2 popped[3]弹出1 popped[4]弹出[]5遍历结束后辅助栈为空返回true。这个例子同时体现了模拟法的一个特点一次循环出栈可能连弹多个元素因为弹出可能触发后续元素继续匹配。再看不合法的情形设popped [3, 4, 5, 1, 2]。压入 1、2、3 后弹出 3i1压入 4 后弹出 4i2压入 5 后弹出 5i3此时pushed已耗尽但栈中剩 [1, 2]栈顶是 2而popped[3] 1无法匹配模拟失败——最终辅助栈非空返回false。三语言实现题目指出 pushed一定是popped的排列因此无需处理两数组长度不同或元素集合不同的情况。以下三版实现与仓库中的实际代码完全一致。Python实现位于 lc_946_validate_stack_sequences.py文件通过 include 包 导入List等类型定义并附带可运行的测试用例class Solution: def validateStackSequences(self, pushed: List[int], popped: List[int]) - bool: stack, i [], 0 for num in pushed: stack.append(num) # num 入栈 while stack and stack[-1] popped[i]: # 循环判断与出栈 stack.pop() i 1 return not stack测试驱动部分使用上文走查的示例test_input_pushed [1, 2, 3, 4, 5] test_input_popped [4, 5, 3, 2, 1] expected_output True slt Solution() result slt.validateStackSequences(test_input_pushed, test_input_popped) print(result)运行该脚本会输出True。Java实现位于 lc_946_validate_stack_sequences.javamain方法中内置了同样的测试用例pushed {1,2,3,4,5}popped {4,5,3,2,1}期望trueclass Solution { public boolean validateStackSequences(int[] pushed, int[] popped) { StackInteger stack new Stack(); int i 0; for (int num : pushed) { stack.push(num); // num 入栈 while (!stack.isEmpty() stack.peek() popped[i]) { // 循环判断与出栈 stack.pop(); i; } } return stack.isEmpty(); } }C实现位于 lc_946_validate_stack_sequences_s1.cpp头文件通过相对路径../include/include.hpp引用公共定义class Solution { public: bool validateStackSequences(vectorint pushed, vectorint popped) { stackint stk; int i 0; for (int num : pushed) { stk.push(num); // num 入栈 while (!stk.empty() stk.top() popped[i]) { // 循环判断与出栈 stk.pop(); i; } } return stk.empty(); } };复杂度分析时间复杂度 O(N)其中 N 为pushed的长度。每个元素最多入栈一次、出栈一次整个模拟过程共执行至多 2N 次出入栈操作空间复杂度 O(N)辅助栈stack最多同时存储 N 个元素极端情况是popped与pushed顺序完全相同全部压完才弹出。小结模拟法的适用场景本题是模拟法的典型应用当题目给出明确的操作规则这里是栈的压入/弹出顺序约束且答案是是否存在某种操作序列满足条件时直接把规则翻译成代码逐拍执行即可。两个容易忽略的细节立即出栈的贪心正确性依赖所有数字不相等这一前提——重复元素会导致同一值存在多个可出栈位置简单的栈顶匹配会失效循环出栈而非单次出栈一次入栈可能触发连续多次弹出如上表中步骤 5 连弹 4 个这是模拟能快进的关键。掌握这个模板后可以将其迁移到其他操作序列合法性判定类问题例如按给定序列执行一组增删操作能否得到目标状态等。仓库中的相关代码位置题解文档selected_coding_interview/docs/946. 验证栈序列.mdPythonselected_coding_interview/codes/python/lc_946_validate_stack_sequences.pyJavaselected_coding_interview/codes/java/lc_946_validate_stack_sequences/lc_946_validate_stack_sequences.javaCselected_coding_interview/codes/cpp/lc_946_validate_stack_sequences/lc_946_validate_stack_sequences_s1.cpp公共类型定义selected_coding_interview/codes/python/include/init.py【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考