引言:最近刷数据结构的题,刷到一组元素入栈,他的出栈顺序有可能是哪些时卡住,之前没有关注此类问题,便写下总结
先通过几个例题讲解下出栈顺序问题
1.
一个栈的入栈序列是a,b,c,d,e则栈的不可能的输出序列是:()
A edcba B decba C dceab D abcde
栈之根本——后进先出(Last In First Out , LIFO)初次接触到这个问题的人,或许会认为入栈abcde,所以出栈只能是edcba所以BCD都不对。
其实是这个问题描述有歧义,应该是分段入栈的顺序,也就是说,可能先入栈a,取出a,入栈b,取出b……,所以D也是可能的。
知道这个意思了以后,就要明确这个问题的矛盾根本所在:第一次出栈d,说明什么?说明a,b,c一定早已入栈(入栈顺序决定的)。那么在出栈d以后,a,b,c的出栈顺序一定是c,b,a,而不用理会中间穿插着出栈了d后面的字符(因为可以再入栈,再出栈嘛)。所以立即选中C,不用犹豫,理由简单:d出栈了,abc一定已经入栈,那么abc只能以cba的顺序出栈,C不符合,OK!
举一个更加直观的例子:
如栈顺序是:1 2 3 4 ,如何正确理解出栈?
(1)入栈顺序是1 2 3 4,就是指这四个数依次入栈:
数据4入栈之前,1 2 3肯定已经入栈了;
数据3入栈之前,1 2肯定已经入栈了,而4还没入栈;
数据2入栈之前,1肯定已经入栈了,而2 3 4还没入栈;
数据1最先入栈,2 3 4还没入栈。
(2)既然入栈顺序是1 2 3 4,3 4入栈的时候,1 2 肯定已经入栈了,怎么会在后面再入栈。
(3)先拿4 3 1 2这个出栈序列来说,4最先出来,说明此时1 2 3(底到顶顺序)还都在栈中;接下来只有3能出栈,3出来后,栈中为1 2(底到顶顺序);再接下来只有2能出栈,所以如果出栈序列前两个是4 3的话,后两个只能是2 1。再看个正确的出栈序列:2 4 3 1;2最先出来,说明它出来时,3 4还没入栈,而1已入栈且还在栈中;接着是4出来,说明此时3也在栈中(3要比4先入栈),此时栈中有1 3(底到顶顺序);然后只能
总之,挨个看出栈序列的数据,根据入栈顺序,分析它出来时,栈中应该还有谁,而有谁还没入栈,然后分析此时可不可能是它出栈。
下面针对蓝桥杯问题,编程来进行分析。
题目:
X星球特别讲究秩序,所有道路都是单行线。一个甲壳虫车队,共16辆车,按照编号先后发车,夹在其它车流中,缓缓前行。
路边有个死胡同,只能容一辆车通过,是临时的检查站,如图所示。
X星球太死板,要求每辆路过的车必须进入检查站,也可能不检查就放行,也可能仔细检查。
如果车辆进入检查站和离开的次序可以任意交错。那么,该车队再次上路后,可能的次序有多少种?
为了方便起见,假设检查站可容纳任意数量的汽车。
显然,如果车队只有1辆车,可能次序1种;2辆车可能次序2种;3辆车可能次序5种。
现在足足有16辆车啊,亲!需要你计算出可能次序的数目。
![](https://img-blog.csdn.net/20160513122124612)
分析题意:此题的类型为N个元素的出栈问题,题意为16个元素的出栈顺序有多少种。
我们把n个元素的出栈个数的记为f(n), 那么对于1,2,3, 我们很容易得出:
f(1)= 1 //即 1
f(2)= 2 //即 12、21
f(3)= 5 //即 123、132、213、321、231
然后我们来考虑f(4), 我们给4个元素编号为a,b,c,d, 那么考虑:元素a只可能出现在1号位置,2号位置,3号位置和4号位置(很容易理解,一共就4个位置,比如abcd,元素a就在1号位置)。
分析:
1) 如果元素a在1号位置,那么只可能a进栈,马上出栈,此时还剩元素b、c、d等待操作,就是子问题f(3);
2) 如果元素a在2号位置,那么一定有一个元素比a先出栈,即有f(1)种可能顺序(只能是b),还剩c、d,即f(2), 根据乘法原理,一共的顺序个数为f(1)* f(2);
3) 如果元素a在3号位置,那么一定有两个元素比1先出栈,即有f(2)种可能顺序(只能是b、c),还剩d,即f(1),
根据乘法原理,一共的顺序个数为f(2) * f(1);
4) 如果元素a在4号位置,那么一定是a先进栈,最后出栈,那么元素b、c、d的出栈顺序即是此小问题的解,即 f(3);
结合所有情况,即f(4) = f(3) +f(2) * f(1) + f(1) * f(2) + f(3);
为了规整化,我们定义f(0) = 1;于是f(4)可以重新写为:
f(4) = f(0)*f(3) + f(1)*f(2) + f(2) * f(1)+ f(3)*f(0)
然后我们推广到n,推广思路和n=4时完全一样,于是我们可以得到:
f(n) = f(0)*f(n-1) + f(1)*f(n-2) + ... +f(n-1)*f(0)
即
![](https://img-blog.csdn.net/20160513121809661)
方法二:
但这只是一个递推公式(若编程实现,需要维护一个一维数组,时间复杂度为O(n^2))。怎么把它转化为通项公式呢,复杂度仅为O(1)?
于是上网搜索一下,原来真的有这么一个公式:C(2n,n)/(n+1) (C(2n,n)表示2n里取n),并且有个名字叫Catalan数。附上wiki的链接,写得太详细了: http://en.wikipedia.org/wiki/Catalan_number
现在的问题就是:怎么从上述的递推公式求出C(2n,n)/(n+1) ? 有兴趣的朋友欢迎留言讨论!
我抽象了下问题,在知乎上问了个问题,其中有一个答案提出了“折现法”,从几何上推出了“n个元素进栈有多少个出栈顺序”这个问题的答案是C(2n,n)-C(2n,n-1),化简一下即得Catalan number。推荐大家看一看。
代码:
public class Main {
// 不用管出站后车的数量和顺序,因为进站顺序和出站顺序已经决定出站时的排序
static int fun(int a, int b) {// a是等待进站的数目,b是站中的数目
if (a == 0)// 此时已全部进站,出站时的顺序只有一种
return 1;
if (b == 0)// 此时车站为空,只能让车进站
return fun(a - 1, 1);
// 有两种走法:1、让一辆车进站 ;2、让一辆车出站
return fun(a - 1, b + 1) + fun(a, b - 1);
}
static int fun(int a) {
return fun(a, 0);
}
public static void main(String[] args) {
System.out.println(fun(16));
}
}
答案:35357670