C++ 栈模拟力扣 946. 验证栈序列每日一题题解-编程实验室

文章目录

一、题目描述
二、为什么这道题值得你花几分钟弄懂？
三、题目解析
四、算法原理
- 如何解决问题？
- 模拟过程
- 细节注意
五、代码实现
- 复杂度分析
六、总结
七、下题预告

一、题目描述

题目链接：力扣 946. 验证栈序列

题目描述：

示例 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 的一个排列

二、为什么这道题值得你花几分钟弄懂？

这道题是栈结构基础应用的标杆题，也是面试中“考察数据结构核心思想”的高频题。它没有复杂的语法陷阱，却能精准检验我们是否真正理解栈“后进先出（LIFO）”的核心特性，是夯实栈基础的必做题。

题目核心价值

栈本质的“试金石”：不考复杂API，只考栈的核心规则——入栈出栈的顺序逻辑。提到栈我们都先想到的就是“后进先出”的定义，如果在这道题上卡壳那就是因为我们没把定义转化为可执行的操作逻辑。
模拟思维的训练场：解题核心是“模拟真实栈操作”，这种“还原执行过程”的思维，是解决所有数据结构应用题的通用思路。掌握它，后续遇到队列、链表的模拟题都能快速上手。
面试的“基础筛选题”：大厂面试常把它当作“暖场题”，考察候选人的基础逻辑。能快速写出简洁解法，说明数据结构基础扎实；反之，只会死记硬背的短板会被直接暴露。
边界场景的考量：它覆盖了“全入栈后出栈”“边入边出”“部分入栈即出栈”等所有栈操作场景，能训练我们考虑问题的全面性，避免因忽略极端情况导致代码漏洞。
代码简洁性的体现：最优解法仅需几行核心代码，能考察我们“用最少代码实现核心逻辑”的能力，完全契合面试中“代码简洁性”的评分标准。

面试考察的核心方向

栈特性的理解深度：能否说清“后进先出”如何体现在入栈出栈序列验证中，而非单纯复述定义。
模拟思维的落地能力：能否将“手动验证栈序列”的过程转化为代码逻辑，这是“想得到”和“写得出”的分水岭。
代码的简洁性与可读性：最优解法逻辑清晰、代码短小，能体现你的编码风格和逻辑抽象能力。
复杂度分析的准确性：能否快速分析出时间/空间复杂度，理解“模拟操作”的代价，这是区分初级和进阶开发者的关键。

掌握这道题，既能彻底吃透栈的核心规则，又能训练“模拟执行”的解题思维。后续遇到栈相关的进阶题，比如表达式计算、括号匹配，都能快速找到解题思路，性价比极高。

三、题目解析

力扣中这道题的题干机翻的已经非人类了，但这道题要考察的其实就是我们在数据结构考试中很熟悉的题型——给一个入栈序列和一个出栈序列，判断后者是否合法。

核心问题可以简化为：按照pushed的顺序把元素一个个放进栈里，能不能在任意时刻弹出栈顶元素，最终得到的弹出顺序和popped完全一致？
这个问题的答案，就藏在栈“后进先出”的规则里——只有栈顶的元素，才有权被弹出。

四、算法原理

本题核心算法是“模拟栈操作”，完全还原真实的入栈出栈过程，用“实际操作”验证序列合法性。思路简单且高效，和我们手动做这类题的思路完全一致。

如何解决问题？

我们在手动做题目的时候脑海中自动的为我们准备一个模拟栈，我们会按照pushed序列的顺序，把元素逐个入栈。
每入栈一个元素后，立刻检查栈顶元素是否等于popped序列的当前待弹出元素。
- 如果相等，就把栈顶元素弹出，同时把popped的指针往后移一位，继续检查新的栈顶。
- 如果不相等，就继续把pushed的下一个元素入栈。
当pushed序列的元素全部入栈后，观察模拟栈的状态。如果栈为空，说明所有元素都按popped的顺序正确弹出，序列合法；如果栈不为空，说明序列非法。

这个思路的本质是：只有当栈顶元素和待弹出元素匹配时，才能弹出，否则必须继续入栈——这完全符合栈“后进先出”的规则。

模拟过程

我们用两个示例完整模拟，覆盖“合法序列”和“非法序列”两种场景，帮你直观理解每一步的栈状态变化。

场景1：合法序列（示例1）
输入：pushed = [1,2,3,4,5]，popped = [4,5,3,2,1]
初始化：

模拟栈stack = []
popped指针mark = 0（指向当前待弹出的元素）

步骤	入栈元素	栈状态	栈顶 vs popped[mark]	操作	mark变化
1	1	[1]	1 vs 4（不相等）	无弹出	0
2	2	[1,2]	2 vs 4（不相等）	无弹出	0
3	3	[1,2,3]	3 vs 4（不相等）	无弹出	0
4	4	[1,2,3,4]	4 vs 4（相等）	弹出4	1
5	5	[1,2,3,5]	5 vs 5（相等）	弹出5	2
6	遍历结束	[1,2,3]	3 vs 3（相等）	弹出3	3
7	-	[1,2]	2 vs 2（相等）	弹出2	4
8	-	[1]	1 vs 1（相等）	弹出1	5

最终栈状态为[]（空），说明序列合法，返回true。

场景2：非法序列（示例2）
输入：pushed = [1,2,3,4,5]，popped = [4,3,5,1,2]
初始化：

模拟栈stack = []
popped指针mark = 0

步骤	入栈元素	栈状态	栈顶 vs popped[mark]	操作	mark变化
1	1	[1]	1 vs 4（不相等）	无弹出	0
2	2	[1,2]	2 vs 4（不相等）	无弹出	0
3	3	[1,2,3]	3 vs 4（不相等）	无弹出	0
4	4	[1,2,3,4]	4 vs 4（相等）	弹出4	1
5	-	[1,2,3]	3 vs 3（相等）	弹出3	2
6	5	[1,2,5]	5 vs 5（相等）	弹出5	3
7	遍历结束	[1,2]	2 vs 1（不相等）	无弹出	3

最终栈状态为[1,2]（非空），说明序列非法，返回false。

细节注意

指针同步：mark指针也就是定位popped[mark]下标的指针必须严格跟随弹出操作推进，确保每次弹出的都是popped序列的当前元素，不能跳跃或回退。
循环弹出：入栈后要循环检查栈顶，而非仅检查一次。比如入栈5弹出后，栈顶变成3，此时仍需检查是否匹配下一个待弹出元素，这是很容易遗漏的点。
栈空判断：遍历完pushed后，直接判断栈是否为空即可，无需额外检查mark是否到末尾——因为题目明确pushed和popped长度相同，栈空等价于所有元素都按顺序弹出。
数据结构选择：用vector模拟栈比用标准库stack更方便，push_back入栈、pop_back出栈、back取栈顶的操作足够高效，代码也更简洁。

五、代码实现

classSolution{public:boolvalidateStackSequences(vector<int>&pushed,vector<int>&popped){vector<int>stack;// 用vector模拟栈，操作更灵活intmark=0;// 指向popped中当前待弹出的元素// 按顺序将pushed的元素入栈for(intnum:pushed){stack.push_back(num);// 循环检查：栈顶元素等于待弹出元素时，弹出并推进指针while(!stack.empty()&&stack.back()==popped[mark]){stack.pop_back();// 弹出栈顶元素mark++;// 待弹出指针后移一位}}// 栈为空说明所有元素都按规则弹出，序列合法returnstack.empty();}};

细节说明

栈的模拟：用vector<int> stack代替STL的stack容器。vector的push_back（入栈）、pop_back（出栈）、back（取栈顶）操作和栈的特性完全匹配，而且代码书写更简洁。
核心循环：
- 外层循环：遍历pushed序列，把每个元素依次入栈，这是模拟入栈的核心步骤。
- 内层循环：每次入栈后，立刻检查栈顶是否和popped[mark]匹配。只要匹配，就弹出栈顶并移动mark，直到栈空或不匹配为止——这个循环是实现“边入边出”的关键。
结果判断：遍历完pushed后，栈为空意味着所有元素都按popped的顺序弹出，返回true；否则返回false。