栈的合法出栈序列判断与卡特兰数规律

最终栈为空，返回 true。如果是示例 2，最后栈会残留元素，返回 false。

二、深入观察：出栈序列的隐藏规律

模拟法能解决问题，但如果笔试时没有编译器，能不能快速口算判断？通过分析多个按照顺序入栈的例子，发现了一个关键规律：

如果入栈是顺序入栈，出栈序列中，任意元素后面比它小的元素，必须保持严格逆序。

2.1 用例子验证规律

例子 1：合法序列 [4,5,3,2,1]

• 看元素 4：后面比它小的元素是 [3,2,1] → 逆序（3>2>1），符合；
• 看元素 5：后面比它小的元素是 [3,2,1] → 逆序，符合；
• 看元素 3：后面比它小的是 [2,1] → 逆序，符合；
• 所有元素都满足，所以合法。

例子 2：不合法序列 [4,3,5,1,2]

• 重点看元素 5：后面比它小的元素是 [1,2] → 顺序（1<2），不符合规律；
• 因此直接判断不合法，和题目结果一致。

再举个合法例子：[3,4,5,2,1]

• 元素 3 后面比它小的是 [2,1] → 逆序；
• 元素 4 后面比它小的是 [2,1] → 逆序；
• 元素 5 后面比它小的是 [2,1] → 逆序；
• 符合规律，确实是合法出栈序列。

2.2 规律的本质：为什么会这样？

栈的核心是'先进后出'（LIFO）。假设元素 A 比元素 B 先压入栈，若 A 还没弹出时 B 就弹出了，那么 A 必须在 B 之后弹出（因为 A 在 B 下面）。

对应到规律：如果元素 X 后面有比它小的元素 Y（Y 比 X 先压入），那么所有比 X 小且在 Y 之后压入的元素 Z，必须在 Y 之前弹出 —— 否则就违反了'先进后出'，这就是'严格逆序'的由来。

三、基于规律的判断代码实现

既然规律成立，我们可以换一种思路写判断代码：先把压入序列的'数值'映射到'压入顺序下标'（比如压入 [2,3,4,5,1]，则 2 的下标是 0，3 是 1，…，1 是 4），再检查弹出序列对应的下标是否满足'任意元素后比它小的元素严格逆序'。

代码实现（C++）

#include <vector>
#include <unordered_map>
using namespace std;

bool IsPoporderByRule(vector<int>& pushV, vector<int>& popV) {
    // 1. 建立'数值→压入下标'的映射，将问题转为'有序下标'的判断
    unordered_map<int, int> valToIdx;
    for (int i = 0; i < pushV.size(); ++i) {
        valToIdx[pushV[i]] = i;
        if (valToIdx.find(popV[i]) == valToIdx.end()) {
            return false;
        }
    }
    // 2. 把弹出序列转为对应的'压入下标'序列
    vector<int> popIdx;
    for (int num : popV) {
        popIdx.push_back(valToIdx[num]);
    }
    // 3. 检查规律：任意元素后比它小的元素是否严格逆序
    int n = popIdx.size();
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (popIdx[j] < popIdx[i]) {
                for (int k = j + 1; k < n; ++k) {
                    if (popIdx[k] < popIdx[i] && popIdx[k] > popIdx[j]) {
                        return false;
                    }
                }
            }
        }
    }
    return true;
}

代码逻辑很简单：通过下标映射，把任意压入序列的问题，转化为'1,2,3,…n'有序压入的问题，再用规律验证即可。

四、探索出栈序列总数：邂逅卡特兰数

解决了'判断合法性'，新问题来了：n 个元素的合法出栈序列有多少种？

比如：

• n=1 → 1 种（[1]）；
• n=2 → 2 种（[1,2]、[2,1]）；
• n=3 → 5 种（[123,132,213,231,321]）；
• n=4 → 14 种；n=5 → 42 种…

4.1 推导尝试

曾尝试基于'严格逆序'规律推导总数：以 n=5 为例，把最大元素 5 放在不同位置，认为 5 后面的元素必须逆序，前面的元素符合卡特兰数。

比如假设 5 在第 3 位，前面有 2 个元素（符合卡特兰数 C₂=2），从 4 个元素选 2 个放在前面（组合数 C₄²=6），总数就是 2×6=12。但实际计算时发现，这样会多算不合法的序列（如 [3,1,5,4,2]，1 和 2 的顺序破坏了逆序），推导需修正。

4.2 卡特兰数：答案的数学本质

这个问题的答案已被数学家卡特兰解决：n 个元素的合法出栈序列数，等于第 n 个卡特兰数，其通项公式为：

C_n = 1/(n+1) * C(2n, n)

其中 C(2n, n) 是组合数，表示从 2n 个元素中选 n 个的方案数。

我们验证一下：

• n=1：结果是 1 → 正确；
• n=2：结果是 2 → 正确；
• n=3：结果是 5 → 正确；
• n=5：结果是 42 → 正确。

4.3 卡特兰数的更多应用（拓展）

卡特兰数不只是栈的专利，它还出现在很多场景：

• 括号匹配：n 对括号的合法匹配数（如 n=2：()()、(()) → 2 种）；
• 二叉树计数：n 个节点的不同二叉树结构数（n=2：2 种）；
• 路径规划：从 (0,0) 到 (n,n) 不穿过对角线的路径数。

五、总结

1. 判断弹出序列合法：两种方法
   • 模拟栈操作：效率 O(n)，适合编程实现；
   • 规律判断：基于'元素后小元素严格逆序'，适合快速口算。
2. 出栈序列总数：第 n 个卡特兰数，公式是 C_n = 1/(n+1) * C(2n, n)。
3. 数学本质：栈的'先进后出'规则，最终转化为卡特兰数的计数问题，体现了算法与数学的紧密联系。