输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。 假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应 的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
思考：考察栈的栈的特性:后入先出 有一个最笨的方法就是列举出所有的出栈入栈顺序 入栈元素:1,2 出栈顺序可能是[1,2],[2,1] 入栈元素:1,2,3 出栈顺序可能是[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,2,1] 唯一不可能存在的情况[3,1,2] 入栈元素:1,2,3,4 出栈顺序:[1,2,3,4],[1,2,4,3],[1,3,2,4],[1,3,4,2],[1,4,3,2] 不可能存在[1,4,2,3] [2,1,3,4],[2,1,4,3],[2,3,1,4],[2,3,4,1],[2,4,3,1] 不可能存在[2,4,1,3] [3,2,1,4],[3,2,4,1],[3,4,2,1] 不可能存在[3,1…] 和 [3,4,1,2] [4,3,2,1] 不可能存在其他情况 … 依次类推
辅助栈，按顺序往栈里塞元素，遇到和弹出序列元素一样的则出栈，最后检查辅助栈是否为空即可 拿入栈序列 [1,2,3]来说，出栈序列 [3,1,2] 第一步: 1入辅助栈，1 ≠ 3,之后辅助栈不操作 2入辅助栈，2 ≠ 3,之后辅助栈不操作 3入辅助栈，3 == 3,辅助栈和弹出栈该元素同时出栈 第二步: 此时: 辅助栈[1,2] 弹出栈[1,2] 从第一个元素循环弹出栈，和辅助栈最后一个元素对比(重复利用栈的后入先出原理) 1 ≠ 2，弹出栈删除1，辅助栈不操作， 2 == 2，弹出栈删除2，辅助栈删除2 最后辅助栈不为空，说明不是该压栈序列的弹出序列,
class Solution1: def IsPopOrder(self, pushV, popV): # write code here if len(pushV) != len(popV):#元素个数不一样 return False assist = []#辅助栈 for i in pushV:#遍历压入栈，符合的最终存放辅助栈 assist.append(i) if i == popV[0]: assist.pop(-1) popV.pop(0) while len(popV) > 0:#遍历弹出栈 if popV[0] == assist[-1]: assist.pop(-1) popV.pop(0) return True if len(assist)== 0 else False