栈压入和弹出顺序

柔情只为你懂 2024-02-18 22:20 67阅读 0赞

**题目描述**

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

第一种方法暴力求解遍历所有的排列形式：

# -*- coding:utf-8 -*-
    #python2.7
    class Solution:
        def IsPopOrder(self, pushV, popV):
            # write code here
            # d是栈 va为序列剩余值
            def allPopV(d, va):
                #判断序列是否为空，如果为空将栈中值全部取出并返回
                if len(va) == 0:
                    return d[::-1]
                else:
                    #如果栈为空，则必须压入栈，然后再次调用自己并返回值
                    if len(d) == 0:
                        d.append(va.pop(0))
                        return allPopV(d[:], va[:])
                    #如果栈不为空，则有两种选择：压栈，出栈
                    else:
                        re1 = []
                        re2 = []
                        va2 = va[:]
                        d2 = d[:]
                        
                        #第一种选择压栈
                        d.append(va.pop(0))
                        re1 = allPopV(d[:], va[:])
                        
                        #第二种选择出栈
                        tempData = d2.pop()
                        #构建出栈后可能情况值
                        for i in allPopV(d2[:], va2[:]):
                            if type(i)== int:
                                i=[i]
                            re2.append([tempData] + i)
                        
                        #将两种情况值合并，判断re1[0]为list是因为：当栈中只有有一个数且序列为空，
                        #再调用allPopV时会返回一个[x]否则会返回[[x],[x]],所以这里必须判断合并方式
                        if re1:
                            if type(re1[0]) is list:
                                for i in re1:
                                    re2.append(i)
                            else:
                                re2.append(re1)
                        return re2
    
            d = []
            #这里做判断popV == c是因为当输入序列长度为1时 程序输出会是一个一维的不能用包含关系判断
            c=allPopV(d, pushV)
            return True if popV in c or popV == c else False