[求助]数据结构方面的证明题.谢谢.
试证明：若借助栈由输入序列1 2……n得到输出序列为P1 P2……Pn(它是输出序列的一个排列)，则在输出序列中不可能出现这样的情形：存在着i <j <k使Pj <Pk <Pi.
[解决办法]
假设存在着i <j <k使Pj <Pk <Pi，因为原数列为1 2……n单增数列，又Pi> Pk,Pi> Pj,所以Pk,Pj必在范围1...Pi-1，同理，因为Pk> Pj，Pj必在1...Pk-1。
所以可得Pi,Pj,Pk在原数列的分布(能不能说显然~)：1...Pj...Pk...Pi...n
要使得输出数列i <j <k，因为i最小，所以Pi应该最先出栈，由上知包含1...Pj...Pk的一个子集必须先入栈，以使得Pi能最先出栈；
此时，栈里1...Pj...Pk...只能为k先出栈，所以在序列中k <j
所以得：i <k <j，和条件矛盾。
