怎么快速判断出栈序列是否正确?再也不用模拟了
(默认入栈序列为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不行。