关于阿里的一道面试题,如果abcdef顺序入栈,那么下面不可能出现的出栈顺序是:
A:fedcba
B:dcbaef // abcd入栈,dcba依次出栈,e入栈,e出栈,f入栈,
C:edcbaf // abcde入栈,edcba依次出栈,f入栈,f出栈
D:dbcaef
对于这样的题,也不是无规律可循,主要就是满足三个条件:
1、在原序列中相对位置比它小的,必须是逆序;
2、在原序列中相对位置比它大的,顺序没有要求;
3、以上两点可以间插进行。
这三个条件咋一看,比较蒙,那么我们就举例来看:
第一个选项
当f第一个出栈时,在原序列中相对位置比它小的,是abcde,他们在这个f之后的出栈中是否是abcde相反的呢?edcba满足条件
当e第二个出栈,在原序列中相对位置比它小的,是abcd,他们在e出栈之后的出栈中是否是abcd相反的呢?dcba满足条件
当d第三个出栈,在原序列中相对位置比它小的,是abc,他们在d出栈之后的出栈中是否是abc相反的呢?cba满足条件
……
第二个选项
当d第一个出栈,在原序列中相对位置比它小的是abc,abc三个元素在d出栈之后的出栈中是否是相反排序的呢?cba满足
当c第二个出栈,在原序列中相对位置比它小的是ab,ab二个元素在c出栈之后的出栈中是否是相反排序的呢?ba满足
当b第三个出栈,在原序列中相对位置比它小的是a,a一个元素在b出栈之后的出栈中是否是相反排序的呢?a满足
当a第四个出栈,在原序列中没有比a更小的啦,所以满足条件。
当e第五个出栈,在原序列中相对位置比它小的是abcd,abcd四个元素在d出栈之后的出栈中是否是相反排序的呢?由于e之后只有f,因此满足条件
第三个选项
当e第一个出栈,在原序列中相对位置比它小的是abcd,abcd四个元素在e出栈之后的出栈中是否是相反排序的呢?dcba满足
当d第二个出栈,在原序列中相对位置比它小的是abc,abc三个元素在d出栈之后的出栈中是否是相反排序的呢?cba满足
当c第三个出栈,在原序列中相对位置比它小的是ba,ba二个元素在c出栈之后的出栈中是否是相反排序的呢?ba满足
当b第四个出栈,在原序列中相对位置比它小的是a,a一个元素在b出栈之后的出栈中是否是相反排序的呢?a满足
当a第五个出栈,在原序列中没有比a更小的了,所以满足条件
第四个选项
当d第一个出栈,在原序列中相对位置比它小的是abc,abc三个元素在b出栈之后的出栈中是否是相反排序的呢?bca不满足