PAT 解题报告 1051. Pop Sequence (25)

题目描述:

一列数, 只能以1, 2, …., N的push 到stack里面, 但是可以再任意时刻pop出一个数字, 问给定一个序列, 是不是一个可行的按照这样的规则可以出现的一个pop序列.

算法分析:

算是模拟题吧, 根据给定的pop序列, 还原push 和 pop的过程, 因为一个pop sequence 只能对应一个唯一的push pop的操作过程, 所以到最后能还原那么这个pop sequence是可行的, 否则不可能, 比如: 3, 2, 1, 7, 5, 6, 4. 这个序列, 那么我们看第一个3, 要pop出3, 那么肯定要先push 1, push 2, push 3, pop 3, 接下来看2, 此时栈顶确实是2那么 pop 2, 接下来1类似, 好了下面一个是7, 那么我们必须要先push 4, push 5, push 6, push 7, 然后pop 7可以得到一个7, 接下来需要5,但是此时栈顶元素是6, 所以这个sequence就是不可能了。 这样的算法基本上市一个线性算法。

注意点:

(全文完,原创文章,转载时请注明作者和出处)


(转载本站文章请注明作者和出处 烟客旅人 sigmainfy — http://www.sigmainfy.com,请勿用于任何商业用途)

Written on April 6, 2013