牛客网刷题笔记：剑指Offer-栈的压入、弹出序列

栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。

说明:
两个序列的长度是相等的

示例一：

输入: pushV = [1,2,3,4,5] , popV=[4,5,3,2,1]
输出: True
解释: 序列[4,5,3,2,1]是[1,2,3,4,5]压栈序列的一个弹出序列

示例二：

输入:  pushV = [1,2,3,4,5] , popV=[4,3,5,1,2]
输出:  False
解释: 序列[4,3,5,1,2]不是[1,2,3,4,5]压栈序列的弹出序列

本题具体思路是获取所有可能的出栈顺序，然后看目标序列是否在可能出栈顺序中。中间过程中纠结了很久tmp的问题，最后通过temp复制tmp数组解决了tmp的记忆性。代码如下：

class Solution:
    def poplist(self,x,ino,tmp,res):
        temp=tmp[:]
        if not x:
            while ino:
                temp.append(ino.pop())
            if temp not in res:
                res.append(temp)
            return 
        self.poplist(x[1:],ino+[x[0]],tmp,res)
        self.poplist(x[1:],ino,tmp+[x[0]],res)
    def IsPopOrder(self, pushV, popV):
        # write code here
        res = []
        self.poplist(pushV,[],[],res)
        if popV in res:
            return True
        return False