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就是不可能了。 这样的算法基本上市一个线性算法。

Written on April 6, 2013