剑指21-栈的压入、弹出序列

题目描述

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

例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

---

思路如下，pushV上的指针左侧的子序列，其实模拟的是栈的变化：

• 对出栈序列popV的第一个元素，用一个指向pushV的指针从左向右找到第一个相等的元素，并将其pushV中删除，并将指针左移一位。
• 然后对popV的下一个元素，用指针继续向右查找，找到想等元素之后，执行与第一步相同的工作。直到pushV的指针超出范围或者popV的元素都被处理完。

class Solution:
    def IsPopOrder(self, pushV, popV):
        i = 0
        while len(popV) > 0:
            # 注意循环条件i+1<=len(pushV)不可少，不然弹出序列某元素不在入栈序列中时，i会往上累加去产生死循环
            while popV[0] not in pushV[:i+1] and i+1<=len(pushV): 
                i += 1
            # 上一句的while循环的终止条件有两个,分别是popV[0] in pushV[:i+1] 和 i+1>len(pushV)。
            # 如果后者成立，则说明popV的元素在pushV中找不到，要返回False
            if i+1 > len(pushV):
                return False
            if popV.pop(0) != pushV.pop(i): 
                return False
            i -= 1
        return True

进一步分析：

• 如果压入序列pushV里有两个相等元素，而弹出序列popV与pushV对应也就有同样的两个相等元素，那么无法判断彼此元素的对应关系。
• 删除元素时pushV和popV都有操作，栈顶元素和弹出元素一定要有相等关系popV.pop(0) != pushV.pop(i)，不然后边肯定对不上。因此该相等关系的判断，不影响最终的判断结果。

---

如下代码的思想和上面版本一样，只是更具体化了，直接构建了个栈。

class Solution:
    def IsPopOrder(self,pushV, popV):
        # write code here
        #边界情况
        if len(pushV) == 0 or len(pushV) != len(popV):
            return False
         
        stack = []
        for num in pushV:
            stack.append(num)
             
            if popV[0] not in stack: #如果第一个弹出的元素不在栈里，则继续压入栈
                continue
            else: # 如果第一个弹出的元素在栈里，则分为是否在栈顶两种情况
                if popV[0] != stack[-1]:# 不在栈顶，肯定错误
                    return False
                else: 
                    # 可能会有多个出栈的情况
                    while len(popV) > 0:
                        if popV[0] != stack[-1]:
                            break
                        else:
                            del stack[-1]
                            del popV[0]
         
        # 遍历了一遍pushV之后，如果popV不为空，则失败
        if len(popV) == 0: 
            return True
        else:
            return False