一个栈的输入序列是12345,则输出序列有多少种,这类题型有什么规律?

一个栈的输入序列是12345,则输出序列有多少种,这类题型有什么规律?
一个栈的输入序列是12345,则输出序列有多少种,这类题型有什么规律?

一个栈的输入序列是12345,则输出序列有多少种,这类题型有什么规律?
可以把这个问题描述为一个二元组表示进栈出栈的状态,(n, 0) 表示有n个元素等待进栈, 0 个元素已进栈,
这相当于问题最初的状况. 接着问题转化为(n-1,1).
可以这么说(n,0) = (n-1,1). 而对于(n-1,1)则相当于(n-1,0)+(n-2,2).
其中(n-1,0)表示栈中的一个元素出栈, (n-2, 2)表示又有一个元素入栈.也就是说,对于(n-1,1),已经有1个进栈的情况,这时候有两种可能：①把栈里面的这个元素出掉,②继续把一个元素进栈,这两种选择导致的序列是不同的,这个是理解的难点和关键点.
这样我们得到了转化公式,把问题一般化,则(n,m)的排列问题可以转化为(n,m-1)+(n-1,m+1)
此时m>=1, 因为必须栈中有元素才可以出栈.
当m=0则(n,0)的问题只能转化为(n-1,1).
当问题为(0, m)时得到递归边界,这个问题的解是只有一种排列.
最终推导的结果是：P2n ＝ C（n 2n）— C（n＋1 2n）=C（n 2n)/(n+1)

这个结果是一个“卡塔兰数”Catalan,在组合数学中有介绍,可以参阅有关资料.

结果=C(5,10)/6= 42

3个元素的情况参考下这个输入ABC的例子,可能比较直观.