题解 | 栈的压入、弹出序列

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param pushV int整型一维数组 
# @param popV int整型一维数组 
# @return bool布尔型
#
class Solution:
    def IsPopOrder(self , pushV: List[int], popV: List[int]) -> bool:
        # write code here
        for i in range(len(popV)): # 遍历出栈序列
            if popV[i] in pushV: # 判断当前元素是否在进栈序列中
                temp = pushV[:pushV.index(popV[i])] # 如果在，再把进栈序列中该元素前的提取出来
            else:
                return False
            # print(pushV.index(popV[i]))
            temp.reverse() # reverse方法修改原数组且没有返回值，所以不要赋值给temp
            # print(temp)
            pushP = 0 # 设置对比指针，用在temp上
            popP = i+1 # 设置对比指针，用在popV上
            while popP<len(popV) and pushP<len(temp): # 循环对比
                if temp[pushP] == popV[popP]: # 如果相同，就一起右移
                    pushP += 1
                popP += 1 # 如果不同，就只动出栈指针
                # print('pushP,popP:', pushP, popP)
            if pushP != len(temp): # 如果是合法的，temp上的指针应该是走完了的，没走完说明没遇到/顺序反了
                return False
            else:
                pushV.remove(popV[i]) # 一定要记得把已经判断合法的元素从入栈序列中删除
        return True

判断方法：对每一个出栈的元素：在进栈序列中这个元素前面的元素都应该是出栈序列中这个元素后面的倒序。

有点绕口，体现为：

进栈： 1 2 3 4 5

出栈： 4 5 3 2 1

对于出栈中的4，进栈中4前面的是1 2 3，那么需要这三个元素在出栈序列中满足：①在4后面 ② 是1 2 3的倒序3 2 1

对于出栈中的5，进栈中5前面的是1 2 3（上一把结束就把4删除了，不然就会干扰这一轮），那么需要这三个元素在出栈序列中满足：①在5后面 ② 是1 2 3的倒序3 2 1

对于出栈中的3，进栈中3前面的是1 2，那么需要这三个元素在出栈序列中满足：①在3后面 ② 是1 2的倒序2 1

对于出栈中的2，进栈中2前面的是1，那么需要这三个元素在出栈序列中满足：①在2后面 ② 是1的倒序1

对于出栈中的1，进栈中1前面的没有了，那么就结束了。

这里需要注意：① 出栈中的元素需要在进栈序列中存在，不然直接False

② 进栈序列需要有元素