C++算法
栈的合法出栈序列判断与卡特兰数规律
探讨栈的弹出序列合法性判断问题。介绍模拟栈操作的常规解法，时间复杂度为 O(n)。总结基于“元素后小元素严格逆序”的快速判断规律。分析 n 个元素的合法出栈序列总数，揭示其与卡特兰数的数学本质关系，并列举括号匹配、二叉树计数等卡特兰数的其他应用场景。
探讨栈的弹出序列合法性判断问题。介绍模拟栈操作的常规解法，时间复杂度为 O(n)。总结基于“元素后小元素严格逆序”的快速判断规律。分析 n 个元素的合法出栈序列总数，揭示其与卡特兰数的数学本质关系，并列举括号匹配、二叉树计数等卡特兰数的其他应用场景。
先从一道经典算法题入手，题目描述如下：
输入两个整数序列，第一个是栈的压入顺序（所有数字不重复），请判断第二个序列是否可能是该栈的弹出顺序。 示例 1：压入 [1,2,3,4,5]，弹出 [4,5,3,2,1] → 合法（返回 true） 示例 2：压入 [1,2,3,4,5]，弹出 [4,3,5,1,2] → 不合法（返回 false）
最直观的思路是'复现'栈的压入和弹出过程，步骤很简单：
#include <vector>
#include <stack>
using namespace std;
bool IsPoporder(vector<int>& pushV, vector<int>& popV) {
size_t popIdx = 0;
stack<int> st;
for (auto& num : pushV) {
st.push(num);
while (!st.empty() && st.top() == popV[popIdx]) {
st.pop();
popIdx++;
}
}
return st.empty();
}
以示例 1 压入 [1,2,3,4,5]，弹出 [4,5,3,2,1] 为例，展示每一步的变化：
| 步骤 | 压入元素 | 栈内元素 | 弹出指针 popIdx | 栈顶是否匹配 popV[popIdx] | 操作后栈内元素 | 操作后 popIdx |
|---|---|---|---|---|---|---|
| 1 | 1 | [1] | 0 | 1≠4 → 不匹配 | [1] | 0 |
| 2 | 2 | [1,2] | 0 | 2≠4 → 不匹配 | [1,2] | 0 |
| 3 | 3 | [1,2,3] | 0 | 3≠4 → 不匹配 | [1,2,3] | 0 |
| 4 | 4 | [1,2,3,4] | 0 | 4=4 → 匹配 | [1,2,3] | 1 |
| 5 | 5 | [1,2,3,5] | 1 | 5=5 → 匹配 | [1,2,3] | 2 |
| 6 | 压入结束 | [1,2,3] | 2 | 3=3 → 匹配 | [1,2] | 3 |
| 7 | - | [1,2] | 3 | 2=2 → 匹配 | [1] | 4 |
| 8 | - | [1] | 4 | 1=1 → 匹配 | [] | 5 |
最终栈为空，返回 true。如果是示例 2，最后栈会残留元素，返回 false。
模拟法能解决问题，但如果笔试时没有编译器，能不能快速口算判断？通过分析多个按照顺序入栈的例子，发现了一个关键规律：
如果入栈是顺序入栈，出栈序列中，任意元素后面比它小的元素，必须保持严格逆序。
栈的核心是'先进后出'（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），再检查弹出序列对应的下标是否满足'任意元素后比它小的元素严格逆序'。
#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=5 为例，把最大元素 5 放在不同位置，认为 5 后面的元素必须逆序，前面的元素符合卡特兰数。
比如假设 5 在第 3 位，前面有 2 个元素（符合卡特兰数 C₂=2），从 4 个元素选 2 个放在前面（组合数 C₄²=6），总数就是 2×6=12。但实际计算时发现，这样会多算不合法的序列（如 [3,1,5,4,2]，1 和 2 的顺序破坏了逆序），推导需修正。
这个问题的答案已被数学家卡特兰解决：n 个元素的合法出栈序列数，等于第 n 个卡特兰数，其通项公式为：
C_n = 1/(n+1) * C(2n, n)
其中 C(2n, n) 是组合数，表示从 2n 个元素中选 n 个的方案数。
我们验证一下：
卡特兰数不只是栈的专利，它还出现在很多场景：
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online