很多学栈结构的人都有过这种体验题目背得滚瓜烂熟知道后进先出但一旦遇到给定入栈序列判断某个出栈序列是否合法就有点发怵。更妙的是等你好不容易写出了一个判定函数旁边有人随口问一句那合法的出栈序列一共有多少种——你大概率会愣住这还真没想过。这篇文章就把这件事讲透。前半部分我们落地一个最稳妥的判定算法解释它为什么对、怎么用后半部分从计数问题自然引出卡特兰数看它是怎么从递推式里长出来的以及它在二叉树、括号匹配、凸多边形剖分这些看起来八竿子打不着的场景里为何都给出同样的答案。无论你是准备算法面试的学生还是写业务代码时偶尔跟树、栈打交道的工程师这条从判断到数学的线都值得走一遍。1. 先谈判定辅助栈模拟法怎么用、为什么对1.1 题目到底在问什么一个栈的有限自由度先把问题说清楚。假设入栈序列是1, 2, ..., n依次入栈中间可以在任意时刻弹出栈顶元素最终得到一个出栈序列。现在给定一个目标序列 p问这个 p 是不是某个合法操作过程的结果。这里的合法二字很关键。栈不是随机出元素的容器它只有栈顶这一个出口。也就是说一个元素能出栈当且仅当它已经在栈里并且所有比它后入栈的元素都已经出去了。每个时刻你只能做两个动作把下一个元素压入栈或者把当前栈顶元素弹出。理解了这两个动作判断合法性其实就是一个模拟问题。我最早刷这道题时第一反应是枚举所有可能的操作序列看能不能碰到目标序列 p。数据量小还能接受n 稍微到 10 就彻底完蛋因为合法操作序列总数本身已经膨胀到了卡特兰数的规模。后来才意识到根本不需要枚举线性模拟一遍就够了。1.2 辅助栈模拟最稳的判定方法模拟的思路非常朴素我用一个辅助栈忠实还原整个入栈、出栈过程然后看这个过程最终能不能恰好产出目标序列 p。具体做法是维护两个东西一个指针in_idx指向下一个尚未压入栈的元素一个辅助栈stack。然后从左到右遍历 p 中的每一个目标元素target如果栈顶恰好是target说明这个元素现在可以出栈直接弹出。如果栈顶不是target那就说明target还没进栈或者还在栈底被压住了。这时候只能从入栈序列里继续压入元素一直压到某个元素等于target为止。如果整个入栈序列都压完了栈顶还不是target那说明target不可能现在出栈序列非法。为什么是贪心的因为在这种判定问题里凡是越晚压入越灵活你在模拟时不需要为了某个未来的元素而提前弹出一个当前并不需要的元素。栈的结构是严格 LIFO 的早弹晚弹只影响后续操作的可能性而能不弹就不弹的策略恰好保留了最多的操作空间。换句话说如果存在任何一条合法的操作路径能让 p 完整产出那么这种见到目标才弹、遇不到就继续压的模拟路径也一定能成功。反过来如果贪心模拟都走不通那其他方案也走不通。这段逻辑值得多读两遍因为它是整个判定算法正确性的核心很多人写代码没问题但被问为什么这么做是对的时说不清楚。1.3 一个合法序列和一个非法序列的完整推演光说理论太干上手推两个例子。以n 5为例入栈顺序是1 2 3 4 5。第一个序列4 5 3 2 1读 4。栈顶空不是 4。从入栈序列依次压入 1、2、3、4此时栈为[1,2,3,4]栈顶是 4弹出。读 5。栈顶是 3不是 5。继续压入 5栈变成[1,2,3,5]栈顶是 5弹出。读 3。栈顶正好是 3弹出。读 2。栈顶正好是 2弹出。读 1。栈顶正好是 1弹出。所有目标元素都依次出栈辅助栈最终为空判定为合法。第二个序列4 5 3 1 2读 4。压入 1、2、3、4弹出 4。读 5。压入 5弹出 5。读 3。栈顶正好是 3弹出。读 1。此时栈是[1,2]栈顶是 2不是 1。入栈序列已经全部压完没有新元素可以压入于是1永远不可能成为栈顶。如果你尝试强行让 1 出栈唯一的办法是让 2 先出但 2 又不在目标序列里后续也无法解释。所以这个序列非法。从这个反例能直观感受到栈底的小元素要是没机会出栈就会把上面的所有元素全部堵住。下面给出一个通用的 Python 实现in_seq和out_seq都作为序列传入def is_valid_stack_permutation(in_seq, out_seq): if len(in_seq) ! len(out_seq): return False in_idx 0 stack [] for target in out_seq: # 栈顶不是 target 时尝试从入栈序列继续压入 while in_idx len(in_seq) and (not stack or stack[-1] ! target): stack.append(in_seq[in_idx]) in_idx 1 if not stack or stack[-1] ! target: return False stack.pop() return not stack注意最后一行不仅要遍历完out_seq还要保证所有压进去的元素最终都弹出来了。如果遍历结束时栈里还有残留说明某个元素进去后根本没按目标序列出来同样非法。2. 看穿局部规律从模拟过程到跳跃出栈约束2.1 模拟过程中露出的大小关系约束模拟法已经能解决问题但它没有告诉我们合法序列凭什么长这样、不合法序列又为什么会被卡住。想回答这个就需要从模拟过程中提炼出一些数学结构。观察一个合法出栈序列一个很明显的现象是从栈里连续弹出的几个元素一定是从栈顶一路往下的。比如上面例子中的4 5 3 2 1最后一段3 2 1就是一次从栈顶到栈底的连续弹出表现为一个连续的递减段。这不难理解因为栈里的元素从栈顶到栈底本来就是按入栈顺序的反向排列你要连续出栈只能逆着入栈顺序往外拿。于是产生了一个直觉上的约束一个较大的元素如果想要出栈它必须等到所有比它更晚入栈、并且还压在它上面的元素都离开。反过来说一个较小的元素如果被一个后入栈的大元素压住了它就只能等那个大元素先走。但这个描述太宽松了实际约束要更精确。我们来看一个真实的非法反例4 5 3 1 2中被卡住的那一幕3 出栈后栈里剩下[1, 2]顶部是 2。此时 1 想要出栈但 2 挡在上面。2 是比 1 后入栈的元素而 1 是更早入栈的底部元素。这个结构告诉我们当一个较小元素还压在栈底时任何比它后入栈的大元素都无法在它之后出栈。换句话说在出栈序列这个线性排列里某些跨越是不允许的。2.2 跳跃出栈为什么必然非法用更形式化的语言描述刚才的卡壳点在目标序列里如果我们看到一个元素 a 出栈之后又看到了一个比 a 更早入栈也就是数值更小假设入栈序列是单调递增的 1 到 n的元素 b那么 b 想要出栈就必须在某个时刻成为栈顶。问题是a 出栈时它右边还可能压着别的元素那些元素可能比 b 大也可能比 b 小。我们拿4 5 3 1 2中 1 的困境来说。入栈序列 1、2、3、4、5 依次进栈当 4 和 5 都已经出栈后栈内顺序从底到顶是1 2 3。3 出栈前1 和 2 都在 3 下面。3 一出栈2 立刻成为栈顶。这时候 1 想出来但 2 是后入栈、却在它上面于是 1 被 2 挡住。如果跳到这个场景的外部视角就是目标序列中出现了较大的 4 和 5 都走掉了结果一个较小的 1 却被另一个较小的 2 堵在中间的荒诞局面。从栈的物理结构来说一个元素只要还没出栈它之后入栈的所有元素都必须先从它上面离开。因此目标序列中任何跨元素的跳跃出栈本质上都违背了这个物理顺序。具体到代码判断时跳跃表现为辅助栈模拟时栈顶不匹配、且入栈序列已经枯竭。2.3 从约束到计数合法序列不是均匀分布的既然出栈序列不是所有 n 个元素的任意排列那合法的排法到底有多少种到这里算法题已经慢慢变成了组合计数题。我们先随手列一下小规模的情况n 1合法序列只有11 种。n 2合法序列有1 2和2 12 种。n 3枚举一下合法序列是1 2 3、1 3 2、2 1 3、2 3 1、3 2 1总共 5 种。注意3 1 2不在其中这正好对应前面 2.1 里说的较小元素被较大元素卡住的场景。1, 2, 5 这个数列很多人会有印象——它和二叉树的形态数、括号匹配数、多边形三角剖分数是一伙的。没错这就是卡特兰数的开头。但光看前几项还不够得拿出能说服人的推导过程。3. 计数问题浮出水面合法序列数量就是卡特兰数3.1 从操作序列看括号匹配要数清合法出栈序列一个很聪明的做法是把每一次操作抽象成符号。假设 push 记为左括号(pop 记为右括号)那么任意一组能完整走完的入栈出栈操作都对应一个由 n 个左括号和 n 个右括号组成的符号序列。比如n 3时的合法出栈序列1 2 3对应的操作是 push、pop、push、pop、push、pop写成括号就是()()()。而3 2 1则是 push、push、push、pop、pop、pop对应((()))。这个对应关系非常干净在任意时刻已经 push 的次数一定不少于已经 pop 的次数否则你想 pop 一个空栈这非法。而任意前缀里左括号数不小于右括号数、最终左右数量相等正是括号匹配的定义。于是合法出栈序列的数量直接等于 n 对合法括号序列的数量。3.2 第一个出栈的元素是谁递推式的诞生括号匹配虽然直观但直接把它翻译成计数公式还需要一个桥梁。更经典的推导是从第一个出栈的元素入手。假设入栈序列为 1, 2, ..., n。设第一个出栈的元素是 k1其中 k 可以是 0 到 n-1 的任意整数。这意味着在元素 k1 入栈之前1 到 k 这 k 个元素已经全部入栈了并且一个都不能弹出否则第一个出栈的元素就不会是 k1。然后 k1 入栈并立刻弹出。接下来的局面很有意思栈里从底到顶是1, 2, ..., k这 k 个元素而尚未入栈的是k2, ..., n。这两部分此后互不干扰——栈里的 k 个元素是一个独立的小栈问题尚未入栈的 n-1-k 个元素是另一个独立的小栈问题。两个子问题的合法出栈序列数量分别是 h(k) 和 h(n-1-k)而且可以任意组合。所以h(n) h(0)h(n-1) h(1)h(n-2) ... h(n-1)h(0)其中 h(0) 1。这就是卡特兰数的经典卷积递推式。n 0 时记作 1表示没有元素可出入栈时只有一种空操作。把前几项代进去算h(0)1h(1)1h(2)2h(3)5h(4)14规律完全吻合。3.3 反射原理与闭式公式递推式虽然简洁但要算第 100 个卡特兰数总不能一层层卷积下去。我们最终需要一个闭式公式。回到括号匹配。n 对括号如果不管合法性任意排列共有 C(2n, n) 种因为只需从 2n 个位置里选 n 个放左括号。合法序列是其中任意前缀左括号数不小于右括号数的那一批。怎么把不合法的排除掉这里用到一个漂亮的几何技巧。把左括号看成向右走一步右括号看成向上走一步那么任意一个括号序列都等价于从 (0,0) 到 (n,n) 的一条路径共 2n 步。合法括号序列要求路径永远不越过对角线 y x。非法路径呢非法路径一定会在某个时刻第一次碰到直线 y x1也就是前缀里右括号比左括号多一个。把到达这条直线之前的路径关于 y x1 反射你会得到一条从 (-1,1) 出发到 (n,n) 的路径。反过来任意从 (-1,1) 到 (n,n) 的路径也必然穿过 y x1反射回去就是一条非法路径。二者一一对应。从 (-1,1) 到 (n,n) 一共要走 n1 步向右第一次从 -1 到 0 也算一步、n-1 步向上总步数是 2n路径数量为 C(2n, n1)。所以合法数量 C(2n, n) - C(2n, n1)。化简一下C(2n, n) - C(2n, n1) C(2n, n) × (1 - n/(n1)) C(2n, n) / (n1)。这就是卡特兰数的闭式公式 h(n) C(2n, n) / (n1)。n 4 时 C(8,4) / 5 70 / 5 14完全正确。你可能注意到反射这种处理在组合数学里很常用它的美感在于把一条复杂的路径必须保持在某个区域约束转化为另一类更简单的路径计数然后用减法一步到位。这也是卡特兰数公式在多种场景里反复出现的深层原因——许多组合对象本质上都可以编码成这类不对角线越界的路径。4. 写代码验身完整实现、对拍脚本与容易翻车的边界4.1 完整工程实现校验、模拟与复杂度理论讲完回到工程。很多教材给的判定代码只处理in_seq 1..n的特殊情形但在实际项目中入栈序列完全可能是一个任意排列甚至是一组对象。前面的is_valid_stack_permutation已经支持任意in_seq不过我建议在真实使用时补上更完整的校验逻辑def is_valid_stack_permutation(in_seq, out_seq): if len(in_seq) ! len(out_seq): return False # 如果元素不允许重复可以做集合一致性校验 if len(set(in_seq)) ! len(in_seq) or set(in_seq) ! set(out_seq): return False in_idx 0 stack [] for target in out_seq: while in_idx len(in_seq) and (not stack or stack[-1] ! target): stack.append(in_seq[in_idx]) in_idx 1 if not stack or stack[-1] ! target: return False stack.pop() return not stack复杂度是稳定的 O(n)每个入栈元素最多被压入一次、弹出一次遍历out_seq一次循环里的 while 加起来的次数不会超过入栈序列长度。辅助栈空间最坏情况下 O(n)。这题有一个非常常见的变体入栈序列固定为 1 到 n出栈序列也是 1 到 n 的一个排列。此时你甚至可以不用in_seq只维护一个计数器next_to_push表示下一个应该压入的数字代码会更简洁但可读性反而不如通用版本。4.2 对拍脚本用暴力验证你的判定函数写完了判定函数怎么确定它真的对所有情况都正确最笨也最可靠的办法是暴力枚举 对拍。对于 n 较小的情况我们可以递归枚举所有合法操作序列得到所有合法出栈序列的集合然后和用判定函数过滤所有全排列得到的结果逐一比对。两边应该完全一致不一致就说明判定函数有 bug。from itertools import permutations def brute_valid_sequences(n): in_seq tuple(range(1, n 1)) results set() def dfs(stack, in_idx, out): if len(out) n: results.add(tuple(out)) return if in_idx n: dfs(stack [in_seq[in_idx]], in_idx 1, out) if stack: dfs(stack[:-1], in_idx, out [stack[-1]]) dfs([], 0, []) return results def check(n): in_seq list(range(1, n 1)) brute brute_valid_sequences(n) filtered {p for p in permutations(in_seq) if is_valid_stack_permutation(in_seq, p)} if brute filtered: print(fn {n}: OK, count {len(brute)}) else: print(fn {n}: MISMATCH) print(brute - filtered:, brute - filtered) print(filtered - brute:, filtered - brute) for n in range(1, 8): check(n)跑一下这个脚本n 1 到 7 的结果应该是 1、2、5、14、42、132、429正好是卡特兰数序列。对拍脚本里我最喜欢的一点是你不用信任自己写的高级算法只需要信任枚举所有操作序列这种几乎不可能错的基础逻辑。新算法对不对跟它一比便知。4.3 最容易翻车的边界情况很多人的判定代码在常规用例上跑得很好一到边界就翻车。我总结几个实际踩过的坑第一长度不一致。out_seq比in_seq短或者长都是非法输入直接返回 False这是最基础的防御。第二元素不一致。如果出栈序列里出现了入栈序列根本没有的元素或者元素数量对不上应该先返回 False。我见过不少实现忽略了这一点导致while循环死循环或者最后得到莫名其妙的 True。第三重复元素。这是最容易忽略的大坑。如果入栈序列是[1, 1, 2]出栈序列是[1, 1, 2]表面看起来合法但你仔细想两个 1 完全相同出栈序列里无法区分到底先出的是哪个 1。这个问题的本质是出栈序列没有唯一地指定每个元素的身份所以题目通常都默认元素互异。如果面试或实际场景碰到重复元素正确的处理方式是把每个元素先加上唯一下标变成(值, 下标)后再做判断否则判定结果没有意义。第四空栈安全。在上面的实现里我已经用not stack or stack[-1] ! target保护了栈为空的情况。如果你自己改写记得在访问stack[-1]前先判断栈是否为空否则直接抛 IndexError。5. 同一条公式的多个面孔二叉树、括号匹配、凸多边形剖分与卡特兰数5.1 卡特兰数的一个分身二叉树个数卡特兰数最经典的出场方式之一是计数不同形态的二叉树。n 个节点能组成多少种结构不同的二叉树答案正是第 n 个卡特兰数 h(n)。这里和出栈序列的联系其实非常自然。给定一棵二叉树的前序遍历序列如果把它当作入栈序列那么这棵树的非递归中序遍历出栈序列正好是一个合法出栈序列。反过来说每个合法出栈序列都能还原成一棵结构唯一的二叉树。两者一一对应所以二叉树形态数自然也是卡特兰数。我之所以强调这个对应关系是因为很多人在刷二叉树计数题时完全没有意识到它和判断出栈序列合法性的题目来源于同一个数学对象。理解这一点后你会发现记忆成本大幅降低遇到n 个节点的二叉树形态数n 对括号匹配数n 个元素的合法出栈序列数你只需要记住一条公式 h(n) C(2n, n) / (n1)以及它们能互相转化。5.2 括号、三角剖分与矩阵连乘除了二叉树卡特兰数在组合数学中还统治着一大票计数问题。n 对合法括号序列的数量上一节已经讲过。凸 n2 边形的三角剖分数量也是卡特兰数。所谓三角剖分是用 n-1 条不相交的对角线把多边形切成若干个三角形。你可能会想这跟栈有什么关系其实可以用一个归纳视角来看选定一条边作为底边底边对应一个三角形顶点这个顶点把原来的多边形切成左右两部分左边是一个 k2 边形右边是一个 (n-k)1 边形两侧剖分数相乘再把所有顶点的选择累加起来——得到的正是之前那个 h(n) Σh(k)h(n-1-k) 卷积递推式。还有矩阵连乘问题n1 个矩阵连乘有几种加括号的方式答案也是 h(n-1) 之类的卡特兰数变体。本质上都是同一种递归二分结构在计数。这些场景看起来毫不相关底层结构却完全同构。这正是卡特兰数的迷人之处它不是一个孤立的公式而是组合爆炸背后那只看不见的手。5.3 识别卡特兰系题目几个实用信号在实际刷题过程中我养成了一个识别卡特兰系题目的习惯分享给你们第一题目要求计数结构不同的对象而不是具体路径。比如二叉树形态数括号序列数出栈序列数多边形剖分数这些对象内部都有递归二分结构。第二手动核算小规模结果。如果 n 0, 1, 2, 3 对应的答案是 1, 1, 2, 5那基本可以断定是卡特兰数再代入 n 4 看看是不是 14基本就实锤了。第三看递推式是否写成 h(n) Σ h(k)h(n-1-k) 的形状。很多动态规划题你把状态转移方程列出来后发现它是卷积形式那大概率不是让你 O(n²) 硬算而是可以直接套 O(n) 或更快的卡特兰通项。我记得有一次做一道数多少种合法的出栈序列变体题很多人上来就写三维 DP我只用卡特兰公式一行算出结果直接把数据范围从 n ≤ 20 推到了 n ≤ 10^5。这种识别能力本质上还是来自对从算法到数学这条路的熟悉。最后再分享一个小技巧面试时如果你的解法里出现了卡特兰数完全可以用第一个出栈元素的位置分类来现场证明一遍递推公式这比背一个闭式公式更能让面试官信服你真正理解了这个问题。别问我怎么知道的我就是这么把一道平平无奇的栈模拟题变成了和面试官聊了二十分钟组合数学的面试现场。
