用结论和画图快速秒杀判断出栈序列是否合法这一类题

相信大家在做和栈相关的题目的时候会遇到判断一个序列是否是合法的出栈序列这一类题,模拟栈的操作是标准解法,但是基础较差的同学可能模拟的时候容易出错,下面我给大家介绍两个结论和一些小技巧用于快速准确的秒杀这类题。

结论

下面我们先给出结论。
结论一:出栈序列中的每个数后面的比它小的数,是按递减排列的。
结论二:最大连续退栈次数等于最长连续递减序列。

实战

可能有些人不理解,我们给出两道例题来理解这两条结论

例1:设 a , b , c , d , e , f a,b,c,d,e,f a,b,c,d,e,f以所给的次序进栈,若在进栈操作时,允许出栈操作,则下面得不到的序列为()
A. f e d c b a fedcba fedcba
B. b c a f e d bcafed bcafed
C. d c e f b a dcefba dcefba
D. c a b d e f cabdef cabdef
我们来看D选项, a , b a,b a,b是比 c c c小的元素,但是 a , b a,b a,b是按递增排列的,所以D选项是不合法的,本题选D

例2:【2010统考真题】若元素 a , b , c , d , e , f a,b,c,d,e,f a,b,c,d,e,f依次进栈,允许进栈、退栈操作交替进行,但不允许连续3次进行退栈操作,不可能得到的出栈序列是()
A. d c e b f a dcebfa dcebfa
B. c b d a e f cbdaef cbdaef
C. b c a e f d bcaefd bcaefd
D. a f e d c b afedcb afedcb
首先我们用结论一会发现如果没有不能连续3次退栈操作那么这四个序列都是合法的。
下面我们根据结论二进行分析
先看A选项,最长连续递减序列为 ( d c ) , ( e b ) , ( f a ) (dc),(eb),(fa) (dc),(eb),(fa),所以最大连续退栈操作为2
B选项,最长连续递减序列为 ( c b ) , ( d a ) (cb),(da) (cb),(da),所以最大连续退栈操作为2
C选项,最长连续递减序列为 ( c a ) , ( f d ) (ca),(fd) (ca),(fd),所以最大连续退栈操作为2
B选项,最长连续递减序列为 ( f e d c b ) (fedcb) (fedcb),所以最大连续退栈操作为5
所以本题选D

我们还可以直接通过画图来更直接看出答案
a , b , c , d , e , f a,b,c,d,e,f a,b,c,d,e,f在坐标轴上分别表示为 1 , 2 , 3 , 4 , 5 , 6 1,2,3,4,5,6 1,2,3,4,5,6
在回来看例1,对于A选项, f e d c b a fedcba fedcba这个序列对应的是 6 − > 5 − > 4 − > 3 − > 2 − > 1 6->5->4->3->2->1 6>5>4>3>2>1
我们画图
《用结论和画图快速秒杀判断出栈序列是否合法这一类题》
对于B选项 b c a f e d bcafed bcafed对应的是 2 − > 3 − > 1 − > 6 − > 5 − > 4 2->3->1->6->5->4 2>3>1>6>5>4,我们画图
《用结论和画图快速秒杀判断出栈序列是否合法这一类题》
大家应该有点感觉了吧,C选项我就不画了,下面我们看看不合法会出现什么情况
我们来看D选项 c a b d e f cabdef cabdef对应的是 3 − > 1 − > 2 − > 4 − > 5 − > 6 3->1->2->4->5->6 3>1>2>4>5>6 《用结论和画图快速秒杀判断出栈序列是否合法这一类题》
我们发现在3下面有两个点呈现了上升趋势,这就是序列不合法会产生的图像。
补充:我们再来看一组序列 d b e c a f dbecaf dbecaf画图
《用结论和画图快速秒杀判断出栈序列是否合法这一类题》
注意这里4下面上升的点不连续,但只要小于该点的后面的点有任意两个点连起来有上升趋势(斜率 k > 0 k>0 k>0),即为不合法序列。

下面我们再来看例2,我们看看结论二在图像上是怎么表现的
对于选项A,序列 d c e b f a dcebfa dcebfa对应 4 − > 3 − > 5 − > 2 − > 6 − > 1 4->3->5->2->6->1 4>3>5>2>6>1
《用结论和画图快速秒杀判断出栈序列是否合法这一类题》
我们发现有三段下降的直线,直线上点的个数就是连续退栈的次数
选项B和C省略,留给读者自己画图体验这种感觉
对于选项D序列 a f e d c b afedcb afedcb对应为 1 − > 6 − > 5 − > 4 − > 3 − > 2 1->6->5->4->3->2 1>6>5>4>3>2
《用结论和画图快速秒杀判断出栈序列是否合法这一类题》
我们看到圈出来的这条连续下降的直线上面有5个点所以进行了5次连续退栈操作

证明

下面我根据这位用户的提问给出结论一的证明
《用结论和画图快速秒杀判断出栈序列是否合法这一类题》
我们用的是反证法
a , b , c a,b,c a,b,c三个元素的相对入栈顺序为 . . . − > a − > . . . − > b − > . . . − > c − > . . . …->a->…->b->…->c->… ...>a>...>b>...>c>...省略号表示中间可能还有其他元素。
假设出栈序列是 . . . c . . . a . . . b . . . …c…a…b… ...c...a...b...因为元素 a , b a,b a,b是在元素 c c c之前入栈的,所以当元素 c c c出栈的时候,元素 a , b a,b a,b必然在栈中,而且元素 a a a在元素 b b b的下面,因为 a a a b b b早入栈(假设下面为栈底,上面为栈顶)所以在出栈的时候必然元素 b b b比元素 a a a先出栈,与假设矛盾

    原文作者:一个人,一座城,等一个人
    原文地址: https://blog.csdn.net/qq_50710984/article/details/113873198
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞