栈的合法出栈序列判断与卡特兰数规律
探讨栈的弹出序列合法性判断问题。介绍模拟栈操作的常规解法,时间复杂度为 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