开头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 确实非法但非法原因是违反了栈顶约束不是“反转后不相等”。错误类型错误逻辑反例正确结论反转比较反转入栈序列后与出栈序列直接比较a1 2 3b2 1 3Yes但反转比较得到 Noif 代替 while每次入栈后最多匹配弹出一次a1 2 3b3 2 1Yes但 if 写法得到 No提前终止某次栈顶不匹配就立刻判定 Noa1 2 3b1 3 2Yes但提前终止会误判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此时栈顶是 2b 的下一个目标也是 2但你却已经离开了 while 循环进入下一轮。可这时入栈序列已经全部处理完没有新的元素可以 push 了最终 j 停在 1输出 No正确答案应该是 Yes。这道题里“连续弹出”不是边界情况而是核心场景。正确的做法是每 push 一个元素之后用 while 把所有能弹出的元素全弹掉直到栈顶与目标不匹配或栈为空为止。换句话说每一次新元素入栈都有可能触发一连串的出栈动作而不是单个动作。这个“if 改 while”的差别也是后面正解的关键。第三个易错写法是“提前终止”。很多人看到栈顶和 b[j] 不匹配就立刻认为这组数据不合法直接输出 No。但栈顶暂时不匹配不代表最终不合法因为后面还有元素没入栈。入栈序列 1 2 3出栈序列 1 3 2 就是例子push 1 之后栈顶是 1匹配弹出j 变成 1push 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步骤操作栈内容自底向上出栈指针 jb[j]1push 11042push 21 2043push 31 2 3044push 41 2 3 4045栈顶 4 匹配pop 41 2 3156push 51 2 3 5157栈顶 5 匹配pop 51 2 3238栈顶 3 匹配pop 31 2329栈顶 2 匹配pop 214110栈顶 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; vectorint in(n), out(n); for (int i 0; i n; i) cin in[i]; for (int i 0; i n; i) cin out[i]; vectorint 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) / (n1)。你可以用 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 代码那么栈这一章你就真正学扎实了。后续再遇到括号匹配、字符串解码、表达式求值你都会感谢在这道题上花掉的时间。