题目
分析
直觉告诉我们，这里涉及到递推（递归）。
首先，如果有0个或者1个元素，只有1种出栈方式。这是初始条件。
如果有n个元素，考虑第i个元素的出栈方式：
- 前面进栈的
i-1个元素，有f(i-1)种出栈方式，后面进栈的n-i元素，有f(n-i)种出栈方式。 - 这两批元素的出栈方式是独立的，所以适用乘法原理：\(f(i-1)\times f(n-i)\)。
进行一些研究，就会发现这个递推公式实际上在计算所谓的卡塔兰数。除了本题的应用外，还有很多实际应用。
答案
思考
这道题就是想清楚两点：
- 递推的出发点：以第
i个元素作为分割，将整个入栈的元素分为两部分（不包括自己）。 - 左右部分的出栈方式可以递推（递归）解决。然后用乘法原理。当然，对所有的方式计数，是要累加的。
这个解法的核心：result += catalan(i - 1) * catalan(n - i);的时间复杂度达到\(O(N^2)\)。可以利用公式来计算卡塔兰数：
\(C(n) = (2n)! / ((n+1)! \times n!) = {2n \choose n} / (n+1)\)
其代码更能简单一些：
long long catalan(int n) {
if (n <= 1) return 1;
// Calculate C(n) = (2n)! / ((n+1)! * n!) = (2n choose n) / (n+1)
// Using the formula: C(n) = (2n * (2n-1) * ... * (n+2)) / (n!)
long long result = 1;
for (int i = 0; i < n; ++i) {
result = result * (2 * n - i) / (i + 1);
}
return result / (n + 1);
}这么一来，时间复杂度就降低到了\(O(N)\)。在n比较大的时候，这两种算法的时间差距还是挺大的。我做了一个比较，对于n = 30：
原始递归实现结果: 4861946401452
优化公式实现结果: 4861946401452
原始递归实现耗时: 1076 纳秒
优化公式实现耗时: 481 纳秒