题解 P1750 【出栈序列】

litc · 2013-10-05 21:36:21 · 题解

设定两根指针l和r，l一开始为1，r一开始为c。每次从l到r找到没被选中过的数中最小的一个打出，并设其为已选中。l移至它前一个未被选中的数，r加一（如果r已经移至序列末尾，则不加一）。反复操作直至所有数都被打出。时间复杂度为o(n^2)。

如果用一些数据结构，本题可被优化成O(nlog2n)。但是对于本题n<=10000，没有必要。