开头
P4387【深基15.习9】验证栈序列，这个题号背后的“深基15”指的是洛谷《深入浅出基础篇》题单第15章“栈”的配套习题，而“验证栈序列”只有一句话：给定一个入栈序列和一个出栈序列，判断这个出栈序列是否真的能由入栈序列靠着栈的后进先出规则生成。我的建议是，所有刚学完栈的基本操作、正在刷深基题单的人都应该亲手写一遍这道题。它表面上是一道模拟题，实际上考察的是你能否把一个抽象约束翻译成一套完整可执行的操作流程。这篇文章我会把这道题从题意、常见错误到正解、代码、边界和同类题型全部拆开讲透，既不跳过推演过程，也不回避洛谷提交时遇到的细节坑。
1. 题目到底在问什么：从“能不能”到“怎么验”
1.1 题面和输入输出格式速读
题目给的数据格式是这样的：第一行一个整数 q，表示一共 q 组询问。接下来每组询问先给一个 n，然后第二行是 n 个整数，代表入栈序列 a；第三行是 n 个整数，代表出栈序列 b。要求判断 b 是否可能是某个合法操作过程产生的输出。每组输出一个 Yes 或 No，注意首字母是大写，具体格式以洛谷题目页为准。
我先说一个很多人会忽略的题面细节：P4387 里的所有数是互不相同的。这个条件不是随便给的，它保证了“栈顶等于出栈序列当前值”这个判断不会出现“两个相同数字到底哪个是哪个”的歧义。如果元素里出现重复，比如入栈序列是 1 2 2，出栈序列也是 1 2 2，你就很难通过简单的模拟判断合法性，因为同一个数值可能来自不同的元素，问题会变成另一道更复杂的题。所以做这道题之前，最好先确认互异性这一点，这对后续算法的正确性至关重要。
输入规模方面，深基题单的题目一般不会把 n 出到特别夸张，但稳妥起见建议按 1e5 级别处理。读入时用 cin 配合 ios::sync_with_stdio(false) 就足够快，不需要手写快读；当然如果你习惯了 scanf 也可以。我自己的建议是能用标准流就用标准流，写题解和比赛时都更不容易因为格式问题出错。
1.2 等价表述：这其实是一个操作过程是否存在的问题
用生活化的方式理解：入栈序列就像一条传送带，零件按 a[0], a[1], a[2] ... 的顺序依次送到你面前。你手里有一个只能放一件东西的箱子，也就是栈。零件到达时，你有两个选择：把它放进箱子，或者把箱子最上面的东西拿出来。但注意，传送带上的顺序不能被改变，箱子里的东西也只能后进先出。出栈序列 b 问的就是：经过一连串这样的操作，能不能让拿出来的顺序恰好和 b 一致。
这个问题也可以反过来想：假设你现在看到出栈序列的第一个元素是 b[0]，那么在它出栈之前，所有排在它前面的入栈元素一定都已经被压进栈里了，而且当时它恰好就在栈顶。这不是一个可以“猜”的过程，而是每个出栈动作发生的时间点都被入栈顺序约束死了。所以验证方式就是把这个过程重新演一遍，看能不能走通。这种“把合法性判断转化为可执行的模拟过程”的思路，是栈序列类问题的核心。
2. 最容易写错的两个半吊子解法：先用反例排除
2.1 “把入栈序列倒过来比一比”为什么是错的
初学者最常见的直觉是：栈不是先进后出吗？那入栈序列是 1 2 3，出栈序列不就应该是 3 2 1 吗？于是有人直接把入栈序列反转，然后和出栈序列做一次相等比较，相等就 Yes，否则 No。这个直觉只对“全部元素先依次入栈，再依次出栈”这一种操作模式成立。
实际情况是，你可以在任意时刻执行出栈操作，根本不需要等全部元素都放进去。比如入栈序列是 1 2 3，出栈序列是 2 1 3，这个序列合法吗？合法的。过程是：1 入栈，2 入栈，2 出栈，1 出栈，3 入栈，3 出栈。输出正好是 2 1 3。但如果按“反转比较”去做，入栈序列反转是 3 2 1，和 2 1 3 明显不相等，于是会把一个合法序列误判成不合法。
反过来再看一个非法序列：入栈 1 2 3，出栈 3 1 2。反转比较时，反转 a 得到 3 2 1，不等于 3 1 2，所以判定为 No。这个结论恰好是对的，但判对的逻辑却站不住脚。3 能第一个出栈，说明 1 和 2 都已经被压进栈里了。3 出栈之后，栈顶是 2，下一个出栈的只可能是 2，而不是 1。所以 b = 3 1 2 确实非法，但非法原因是违反了栈顶约束，不是“反转后不相等”。
| 错误类型 | 错误逻辑 | 反例 | 正确结论 |
|---|---|---|---|
| 反转比较 | 反转入栈序列后与出栈序列直接比较 | a=1 2 3，b=2 1 3 | Yes，但反转比较得到 No |
| if 代替 while | 每次入栈后最多匹配弹出一次 | a=1 2 3，b=3 2 1 | Yes，但 if 写法得到 No |
| 提前终止 | 某次栈顶不匹配就立刻判定 No | a=1 2 3，b=1 3 2 | Yes，但提前终止会误判 |
2.2 “入栈一次匹配一次”为什么不够
还有一种常见写法：遍历入栈序列，push 一个元素后，用 if 判断栈顶是否等于出栈序列当前项，相等就 pop 一次。这个写法在不少数据上是能过的，但只要遇到连续弹出的场景就翻车。比如入栈序列 1 2 3，出栈序列 3 2 1。正确过程是：依次 push 1、push 2、push 3，然后连续 pop 3、pop 2、pop 1。如果每 push 一次只允许 pop 一次，那 push 3 之后弹出 3，此时栈顶是 2，b 的下一个目标也是 2，但你却已经离开了 while 循环，进入下一轮。可这时入栈序列已经全部处理完，没有新的元素可以 push 了，最终 j 停在 1，输出 No，正确答案应该是 Yes。
这道题里“连续弹出”不是边界情况，而是核心场景。正确的做法是：每 push 一个元素之后，用 while 把所有能弹出的元素全弹掉，直到栈顶与目标不匹配或栈为空为止。换句话说，每一次新元素入栈，都有可能触发一连串的出栈动作，而不是单个动作。这个“if 改 while”的差别，也是后面正解的关键。
第三个易错写法是“提前终止”。很多人看到栈顶和 b[j] 不匹配，就立刻认为这组数据不合法，直接输出 No。但栈顶暂时不匹配不代表最终不合法，因为后面还有元素没入栈。入栈序列 1 2 3，出栈序列 1 3 2 就是例子：push 1 之后栈顶是 1，匹配，弹出，j 变成 1；push 2，此时栈顶是 2，但 b[1] 是 3，不匹配。如果在这一步就 break 并输出 No，就错了。正确的做法是继续 push 3，让 3 入栈后弹出，再把 2 弹出来。
3. 正解的核心逻辑：指针加栈顶的 while 循环
3.1 整体思路一句话讲完
用两个指针分别指向入栈序列和出栈序列的当前位置。遍历入栈序列，把当前元素压入栈中；每压入一个元素，就用 while 检查栈顶是否等于出栈序列指针指向的目标值，相等就弹出并让出栈指针后移一位。入栈序列全部处理完之后，如果出栈指针已经走到 n，说明所有出栈元素都被逐个匹配成功，输出 Yes，否则输出 No。
这套模拟的核心变量只有两个：for 循环里的 i 表示入栈序列处理到哪个位置，j 表示出栈序列已经匹配到哪个位置。下面用一个具体例子推演完整过程。假设入栈序列是 1 2 3 4 5，出栈序列是 4 5 3 2 1：
| 步骤 | 操作 | 栈内容（自底向上） | 出栈指针 j | b[j] |
|---|---|---|---|---|
| 1 | push 1 | 1 | 0 | 4 |
| 2 | push 2 | 1 2 | 0 | 4 |
| 3 | push 3 | 1 2 3 | 0 | 4 |
| 4 | push 4 | 1 2 3 4 | 0 | 4 |
| 5 | 栈顶 4 匹配，pop 4 | 1 2 3 | 1 | 5 |
| 6 | push 5 | 1 2 3 5 | 1 | 5 |
| 7 | 栈顶 5 匹配，pop 5 | 1 2 3 | 2 | 3 |
| 8 | 栈顶 3 匹配，pop 3 | 1 2 | 3 | 2 |
| 9 | 栈顶 2 匹配，pop 2 | 1 | 4 | 1 |
| 10 | 栈顶 1 匹配，pop 1 | 空 | 5 | 结束 |
最后 j = 5 = n，判定合法。注意第 7 步 pop 完 5 之后，栈顶变成 3，而 b 的下一个值也是 3，所以 while 会继续执行第 8 步；这一连串动作正是“if 改 while”的原因。
再看一个非法例子：入栈序列 1 2 3 4 5，出栈序列 4 3 5 1 2。前面几步和上一个例子类似，直到 4 和 3 都被弹出后，栈底还剩 1 2，出栈指针指向 b[2] = 5。继续 push 5，栈顶 5 匹配，弹出，j 变成 3。此时 b[3] = 1，栈顶是 2，不匹配。入栈序列已经全部处理完，但 j 只有 3，不等于 5，于是判定为非法。用手推一遍这个例子，就能直观理解“为什么这个序列不可能诞生”：2 明明压在 1 上面，不可能越过 1 先出栈。
3.2 为什么这个模拟是完备的：关于指针 j 的单调性
很多人在理解这道题时最大的困惑是：凭什么模拟一遍就能断定“合法”或“非法”？这里的关键在于出栈指针 j 永远不回头。当某个元素被弹出并匹配了 b[j]，它在出栈序列中的位置就固定了，之后不可能再变。因为出栈序列是实际输出的顺序，已经输出的元素不会重新出现。于是整个模拟变成一个单向推进的过程：入栈序列不断供应新元素，栈不断消费可匹配的元素，出栈指针不断前进。如果最终 j 能走完 n 个元素，那说明我们成功构造了一个满足所有约束的操作序列；如果走不完，说明在某一步出现了“栈顶无法匹配，且没有更多元素可以入栈”的死局，而这个死局恰恰证明了不存在合法方案。
这个性质还能解释为什么不需要回溯。你可能会想：当前不匹配，是不是可以通过提前弹出某个更早的元素来避免？但栈只能在栈顶操作，如果更早的元素需要出栈，它必须等到压在它上面的元素全部出栈之后，顺序被完全锁死。因此不存在“换一条路走”的空间。栈的模拟没有任何分支，它是确定性的：入栈序列给定的瞬间，所有元素的入栈次序就固定了，出栈动作只能由 b[j] 决定。想通这一点，你就能明白为什么这个问题是 O(n) 的。
4. 完整代码实现与洛谷提交时容易翻车的细节
4.1 一份可以直接提交的 C++ 代码
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int q; cin >> q; while (q--) { int n; cin >> n; vector<int> in(n), out(n); for (int i = 0; i < n; ++i) cin >> in[i]; for (int i = 0; i < n; ++i) cin >> out[i]; vector<int> stk; stk.reserve(n); int j = 0; for (int i = 0; i < n; ++i) { stk.push_back(in[i]); while (j < n && !stk.empty() && stk.back() == out[j]) { stk.pop_back(); ++j; } } cout << (j == n ? "Yes" : "No") << '\n'; } return 0; }这份代码用的是 vector 模拟栈，而不是 C++ 标准库的 stack。原因很简单：vector 配合 reserve 可以提前分配好空间，避免频繁扩容，评测时整体性能更稳定；而且 stk.back() 和 stk.pop_back() 写起来也不比 stack 的 top 和 pop 麻烦。当然，直接用 stack 也完全能过，只是我个人在写这类题时更偏好 vector 模拟栈，调试时还能直接遍历栈内容。
我在 while 条件里专门写了 j < n，这是个容易被忽略的细节。如果不写，假设 j 已经等于 n，循环条件会访问 out[j]，也就是 out[n]，这是越界访问，虽然大多数评测环境里可能不会立刻报错，但属于未定义行为。尤其是当出栈序列中有不存在于入栈序列的元素时，这种越界是可能出现的。加上 j < n 之后，逻辑上自洽，任何情况下都不会越界，多写一个条件不会影响性能，推荐保留。
4.2 多组数据场景下的常见提交错误
这道题是多组测试数据，每组的 n 和序列都不同，最容易踩的坑就是栈没有清空。如果你把栈定义在 while(q--) 内部，每组重新创建，自然不会残留；但如果你把栈定义在 main 开头、在主循环里重复使用，就必须在每组数据开始时清空。用 vector 模拟栈的话，直接 stk.clear() 即可。同样的道理，j 这个出栈指针也必须每组重新归零。很多人遇到“第一组数据对，第二组数据莫名其妙地错”的情况，十有八九就是状态没有重置。
另一个高频错误是读入顺序搞反。题目先给出入栈序列，再给出出栈序列，代码里我用 in 和 out 两个 vector 来区分。有点同学把第二行读进出栈序列，第三行读进入栈序列，模拟结果自然全错。这种错误很难排查，因为你盯着一组数据看时，逻辑上总觉得“栈顶为什么和理想中的不匹配”。所以写读入时建议变量名起成 in/out 或者 pushSeq/popSeq，尽量不要笼统地用 a/b。
输出格式也要注意：“Yes”和“No”的首字母是大写的，有些题目是“YES”全大写，有些是“Yes”首字母大写，还有的是“yes”全小写。P4387 要求的是首字母大写形式。这看起来是个很蠢的错，但每次这类题目的提交记录里都会有人因为这个 WA 一两发。我的习惯是：复制题目样例输出里的字符串，而不是凭记忆敲。
4.3 不同语言实现的踩坑差异
如果用的是 Python，栈可以用列表模拟，pop() 默认弹出末尾，list 模拟栈非常自然。主要注意两点：一是每组数据要重新初始化 stack = []；二是输入用 sys.stdin.buffer.read() 按整数一口气读完，再用索引读取，否则 q 组大数据时 Python 的逐行 input 会比较吃力。用 C 语言写的话，需要自己维护一个数组和栈顶指针 top，模拟压栈出栈；这时候尤其要注意数组大小开够，我一般直接静态数组开满题目上限再加 5，避免动态分配和越界。
C 语言的代码骨架大概是：int stk[N], top = 0; 每次入栈 stk[++top] = in[i]; 每次出栈 top--; 判断栈顶就是 stk[top]。其他逻辑和 C++ 完全一致。不过如果你已经在用 C++，我建议直接沿用上面的 vector 写法，简洁且不容易犯数组越界的错。
5. 复杂度分析：为什么这道题根本不需要回溯
5.1 时间复杂度的直观证明
这个算法的复杂度是 O(n) 时间、O(n) 空间。很多人乍一看会觉得 while 循环嵌在 for 循环里面，复杂度不应该是 O(n^2) 吗？其实不是。关键在于每个元素只会被压入栈一次，也只会被弹出一次。for 循环执行 n 次 push，而 while 循环里的 pop 操作总次数最多是 n 次，因为栈里一共就 pusk 进去 n 个元素。所以无论 for 和 while 怎么嵌套，总操作步数是 2n 级别的，复杂度就是线性。
如果题目改成“入栈序列固定，出栈序列允许重复选择弹栈时机”，那核心矛盾还是栈顶约束，依然是线性模拟能解决。真正会让复杂度失控的做法是拿回溯递归去枚举所有可能的出栈顺序，比如用 DFS 尝试每一步是入栈还是出栈，那样最坏情况是指数级的。也是因为这一点，我强烈建议做这道题时直接写模拟，不要想太多“高级算法”。
5.2 n 的最大值和两个序列长度不一致的情况
洛谷 P4387 的 n 一般给到 1e5 级别，q 也不大。这个规模下，O(n) 的模拟完全够用。但如果是面试场景，面试官可能还会加问：如果出栈序列里有一个数字根本不在入栈序列中，你的程序会怎样？答案很简单：那这个数字永远无法匹配，j 最终走不到 n，输出 No。上面的代码天然处理了这种情况，不需要额外判断。
还有一类变种是入栈序列和出栈序列长度不相等。P4387 原题保证长度相等，但 LeetCode 946 里同样保证。如果不保证，最简单的方法是开头先判断两个序列长度是否相等，不相等直接 No。后续的逻辑也不用改，因为 j 最多走到出栈序列的长度，而 for 循环按入栈序列长度执行。不过在 P4387 的题面下不用考虑这个问题，知道有这回事即可。
6. 同类题型的通用套路：从验证栈序列到括号匹配与卡特兰数
6.1 括号匹配和验证栈序列其实是同一个模型
栈序列验证的思路可以迁移到不少题目上。最典型的是括号匹配：遍历字符串，遇到左括号就压栈，遇到右括号就检查栈顶是不是对应的左括号，是则弹出，否则非法。这和验证栈序列的“入栈元素等于目标值就弹出”本质上是同一种节奏。区别只在于验证栈序列时，你有一个显式的出栈序列来告诉你“什么时候该弹出”；而括号匹配时，是右括号本身在告诉你“现在弹出，且弹出内容必须匹配”。
理解了这一点，你就知道为什么递归下降解析、表达式求值、DFS 回溯里的撤销操作都反复使用栈。它们做的都是同一件事：维护一个“当前还没处理完、但必须按后进先出顺序处理”的集合。P4387 把这个模型单独拎出来考，就是为了让你在写更复杂的栈应用之前，先把这个最朴素的“push 后连续 pop”节奏练熟。
6.2 出栈序列的合法数量与卡特兰数
更深一层的问题是：对 n 个互不相同的元素，固定入栈序列后，合法出栈序列一共有多少种？答案是卡特兰数。当 n = 3 时，3 个元素的全排列有 6 种，但合法出栈序列只有 5 种：123、132、213、231、321，唯一不合法的是 312。这正好和我们前面推演的例子对上了。
卡特兰数的递推式 C_n = sum(C_i * C_{n-1-i})，或者直接用组合数公式 C_n = C(2n, n) / (n+1)。你可以用 P4387 的模拟过程去逐一验证小 n 情况下合法序列的数量，这比直接背公式更能加深理解。如果把入栈记为 +1，出栈记为 -1，合法出栈序列对应一个前缀和永远非负的括号序列，这又回到了括号匹配的模型。这不算竞赛考纲里的高频内容，但对理解栈的约束非常有帮助。
6.3 其他可以套用的场景：火车调度和双栈排序
火车调度问题也是同一类：一列火车按顺序进入一段调度线，调度线只能从一端进出，问你给定的出站顺序能不能实现。这在数据结构教材里几乎就是验证栈序列的换皮版本。理解了 P4387，这个场景你可以直接秒杀。双栈排序则是更复杂的问题：用两个栈配合出栈，判断能否完成排序，这类题就需要单独分析了，因为多了一个栈就让决策出现分支，不再是无脑模拟。
我的建议是：刷题时每做完一题，花几分钟想一想“这题的模型还能迁移到哪”。P4387 迁移范围极广，从括号匹配到函数调用栈都不离开这个约束模型。把基础的 push-while-pop 节奏练成肌肉记忆，你后面遇到表达式求值、单调栈、编译器匹配括号等问题时都会轻松很多。
7. 复盘：我从这道题里提炼的三个做题习惯
7.1 判断“是否存在合法操作序列”时，优先尝试直接模拟
我最早做这道题时也想找公式，比如用逆序对或者某个数学条件去判断合法性，结果想半天也想不出一个简洁的充要条件。后来发现最朴素的想法反而是最正确的：与其推算合法性，不如直接模拟整个过程，模拟成功就是合法，模拟失败就是不合法。这个思路可以推广到很多“是否存在合法路径”“是否能通过某种操作达到目标”的问题上。如果状态的转移是确定性的，直接模拟往往就是最优解。
7.2 写模拟前先明确所有状态变量的含义
写 P4387 之前，我建议先在纸上写下三个东西：入栈指针 i、出栈指针 j、栈 stk 各自的含义。i 表示下一个待入栈的元素下标，j 表示下一个待匹配的出栈元素下标，stk 是当前尚未弹出的元素。状态明确之后，循环里每一步做什么就非常清晰：把 in[i] 压入栈，然后尽可能让栈顶去匹配 out[j]。很多代码写得混乱，本质上是因为连 j 代表什么都没想清楚就开始敲键盘。
我在调试时常用的方法是在关键位置打印 j 和栈的内容，比如每组数据跑完都输出一下 j 的值。只要看到 j 在某一步突然不动了，而 for 循环已经结束，就能判断出是连续弹出逻辑出了问题，还是栈没清空。用笔和纸手动推演一组小数据，也比直接盯代码找 bug 要快得多。
7.3 边界条件单独列出来测一遍
最后一个习惯是把边界条件当成独立用例来测。n = 1 时，入栈 5 出栈 5 必须 Yes；入栈 5 出栈 6 必须 No。n = 2 时，入栈 1 2 出栈 2 1 必须 Yes；入栈 1 2 出栈 2 3 必须 No。栈空时访问 top 是未定义行为，所以 while 判空必须写在访问栈顶的前面。j 可能越界，所以 while 条件里 j < n 必须写在 stk.back() == out[j] 的前面。这些看起来是琐碎的防御性代码，但正是它们保证你能在一次提交内通过所有数据点。
我在实际写 P4387 的过程中，最深的体会就是：这道题没有复杂的算法，但它逼你把“栈的约束”理解到能手动推演的程度。如果你能把上面的模拟过程不看代码复述一遍，再独立写出 AC 代码，那么栈这一章你就真正学扎实了。后续再遇到括号匹配、字符串解码、表达式求值，你都会感谢在这道题上花掉的时间。
