怎么快速判断出栈序列是否正确?再也不用模拟了
  • 板块学术版
  • 楼主AKPC
  • 当前回复7
  • 已保存回复7
  • 发布时间2022/6/6 13:11
  • 上次更新2023/10/27 23:52:52
查看原帖
怎么快速判断出栈序列是否正确?再也不用模拟了
540363
AKPC楼主2022/6/6 13:11

怎么快速判断出栈序列是否正确?再也不用模拟了

(默认入栈序列为1,2,3,4,5......n)

首先,每次找出三个在出栈序列中连续的数a,b,c并对它们进行从小到大排序,有六种情况(就不一一列举了)

如果排序结果为b,c,a(a大b小c中等),就能判断这个出栈序列是错的!如果重复执行n-2次都不是这样就是对的了!

那为什么呢?

假设出栈序列是3,1,2的话,会怎么样?
我们想要让3排在上面,需要一次性把1,2,3全部入栈,此时栈中从上到下排序为3,2,1
我们将3取出来,接着需要取1,但是1被2覆盖了,必须先拿2,所以3,1,2不行。

2022/6/6 13:11
加载中...