311 出栈序列和入栈序列的关系

出栈序列和入栈序列的关系

出栈元素不同排列的个数

n 个不同元素入栈时，出栈元素不同排列的个数满足 卡特兰数（Catalan number），通项公式为

$$C_n=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$$

递推公式为

$$C_{n+1}=\sum _{i=0}^n{C}_i{C}_{n-i}(n\ge 0)$$

出栈序列的合法性判断

对于入栈序列为 1, 2, 3, …, n，出栈序列必须满足：

• 对于出栈序列中任意一个元素，其后面所有比它小的元素必须按递减顺序排列。换言之，若元素 a 在出栈序列中位于元素 b 之前，且 a < b，则 b 后面出现的所有比 b 小的元素的顺序必须是逆序的
• 对于比该元素大的元素，出栈顺序没有严格限制，可以是任意顺序