出栈序列与卡特兰数

问题模型

给定 n 个不同元素按固定顺序进栈，每个元素都必须进栈一次、出栈一次，问可能得到多少种合法出栈序列。这个数量就是第 n 个卡特兰数。

定义

卡特兰数最核心的是它描述的一类结构：空结构算一种；任意非空结构都能唯一拆成“左边一个同类结构 + 右边一个同类结构”。

对一个含有 n 对 push-pop 的非空合法序列，最左边一定是一个 push。这个 push 会被后面某个唯一的 pop 匹配。若这一对 push/pop 内部包住了 i 对 push-pop，那么这一对结束后右侧就剩下 n - 1 - i 对 push-pop。

即

$$
\text{push}\ (i\text{ pairs})\ \text{pop}\ (n-1-i\text{ pairs})
$$

也就是：

第一段 i 对 push-pop 是外层第一对 push/pop 里面包住的部分；
第二段 n - 1 - i 对 push-pop 是外层第一对结束后右侧剩下的部分；
两段都必须仍然是合法的同类序列。

即：一个规模为 n 的合法序列，被第一对匹配的 push/pop 切成一个规模为 i 的子问题和一个规模为 n - 1 - i 的子问题。

递推公式

设 $C_n$ 表示含有 n 对 push/pop 的合法序列数量。

空序列只有一种：

$$
C_0 = 1
$$

对 n >= 1，固定第一对匹配的 push/pop 内部含有 i 对操作，则序列形如：

$$
\text{push}\ (i\text{ pairs})\ \text{pop}\ (n-1-i\text{ pairs})
$$

内部的i对与外面的n-1-i对依然一定是合法的操作，满足对$C$的定义。

即左侧子序列有 $C_i$ 种选法，右侧有 $C_{n-1-i}$ 种选法。对这个固定的 i，共有$C_i C_{n-1-i}$种合法序列。

枚举 i = 0, 1, ..., n - 1，就得到：

$$
C_n = \sum_{i=0}^{n-1} C_i C_{n-1-i}
$$

也就是：

$$
C_n = C_0C_{n-1} + C_1C_{n-2} + \cdots + C_{n-1}C_0
$$

判断具体序列是否合法

卡特兰数只回答“有多少种”，不直接回答“某个序列是否合法”。判断具体出栈序列仍要模拟栈。

基本规律是：若 x 入栈后尚未出栈时 y 入栈，则 y 一定先于 x 出栈。

易错点

分治定义中的 i 可以取 0，n - 1 - i 也可以取 0，所以递推里需要 C_0 = 1 表示空序列。
卡特兰数适用于进栈顺序固定、所有元素都入栈一次且出栈一次的普通栈模型。
若题目改变操作限制，例如使用双端队列，合法输出序列数量通常不再直接套普通栈的卡特兰数。