中午吃饭的时候听到隔壁桌在聊一道题，当时没想出来。 事后查了些资料，记录一下。

问题

一个栈的进栈序列为 1, 2, 3, 4, ..., n, 出栈序列有多少种情况？

解题思路

假设计算情况数的函数为\(f(n)\),

1) 如果元素1第一个出栈，那么情况一定是1进栈然后立马出栈，此时还剩 2, 3,..., n，有\(f(n-1)\)种情况。

2) 如果元素1第二个出栈，那么有一个元素比1先出栈，这个元素只能是2，此时还剩3, 4, ..., n,有\(f(1) \cdot f(n-2)\)种情况。

3) 如果元素1第三个出栈，那么有两个元素比1先出栈，这个元素只能是2或3，此时还剩4, ..., n,有\(f(2) \cdot f(n-3)\)种情况。

…

n-1) 如果元素1第n-1个出栈，那么有n - 2个元素比1先出栈，这个元素可能是{2, 3, 4, ..., n - 1}中的一个，剩下n，有\(f(n-2) \cdot f(1)\)种情况。

n) 如果元素1第n个出栈，那么有n - 1个元素比1先出栈，这个元素可能是{2, 3, 4, ..., n}中的一个，有\(f(n-1)\)种情况。

这样一来，可以推导出，

其实这个函数是卡塔兰数 它的公式是，

用递归实现的时间复杂度会是\(O(N^2)\)，而借助记忆可以省掉重复计算，而如果借助上面的公式，也可以写出非常简洁的递归或者迭代，下面给出两种计算方法：

借助记忆的 DP， 由于每次求C[K]都需要C[0], C[1], ..., C[K-1]，所以没办法使用动滚动数组：

long C(int n) {

    long[] C = new long[n + 1];
    C[0] = 1L;
    for (int i = 1; i < n + 1; i ++) {
        int c = 0;
        for (int j = 0; j < i; j ++) {
            c += C[j] * C[i - j - 1];
        }
        C[i] = c;
    }
    return C[n];
}

借助上面的公式，可以推出\(C_n\)与\(C_{n-1}\)的递推公式，

借助这个递推关系可以递归实现：

long C(int n) {
    if (n == 0 || n == 1) {
        return 1;
    }
    return C(n - 1) * 2 * (2 * n - 1) / (n + 1);
}

由于以上的递归是「自顶向下」的，造成许多重复计算。 优化一下，

long C(int n) {
    if (n == 0 || n == 1) {
        return 1;
    }
    long temp = 1;
    for (int i = 2; i < n + 1; i++) {
        temp = temp * (2 * (2 * i - 1) / (i + 1));
    }
    return temp;
}

相关的问题

栈序列相关

这道题会让人想到 946. 验证栈序列，这道题比较容易想到的解法是用一个栈模拟进栈和出栈，这样做的时间复杂度是\(O(N)\)，因为每个元素只会进栈一次、出栈一次，空间复杂度也是\(O(N)\)，需要一个栈的额外空间。

其实还有一个空间复杂度为\(O(1)\)的解法，可以将pushed数组作为栈空间使用，具体可以参见这篇题解。

卡特兰数相关

后来我在leetcode看到这篇文章，讲解的更详细。