我的个人微信公众号：Microstrong

微信公众号ID：MicrostrongAI

公众号介绍：Microstrong(小强)同学主要研究机器学习、深度学习、计算机视觉、智能对话系统相关内容，分享在学习过程中的读书笔记！期待您的关注，欢迎一起学习交流进步！

个人博客：https://blog.csdn.net/program_developer

知乎专栏：https://zhuanlan.zhihu.com/Microstrong

---

题目链接：

https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&tqId=11174&tPage=2&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking

题目描述：

解题思路：

        解决这个问题很直观的想法就是建立一个辅助栈，把输入的第一个序列中的数字依次压入该辅助栈，并按照第二个序列的顺序依次从该栈中弹出数字。
        以弹出序列 4、 5 、 3、 2、 1 为例分析压栈和弹出的过程。第一个希望被弹出的数字是 4，因此4需要先压入到辅助栈里面。压入栈的顺序由压栈序列确定了，也就是在把 4 压入进栈之前，数字 1 、 2、 3 都需要先压入到栈里面。此时栈里包含 4 个数字，分别是 1 、 2、 3、 4，其中4位于栈顶。把4弹出栈后，剩下的三个数字是1、2和3。接下来希望被弹出的数字是5， 由于它不是栈顶数字，因此我们接着在第一个序列中把 4 以后数字压入辅助栈中，直到压入了数字 5。这个时候5位于栈顶，就可以被弹出来了。接下来希望被弹出的三个数字依次是3、2和1。 由于每次操作前它们都位于栈顶，因此直接弹出即可。表1总结了本例中入栈和出栈的步骤。

表1 压栈序列为1、2、3、4、5，弹出序列为4、5、3、2、1对应的压栈和弹出过程

步骤	操作	栈	弹出数字
1	压入1	1
2	压入2	1、2
3	压入3	1、2、3
4	压入4	1、2、3、4
5	弹出	1、2、3	4
6	压入5	1、2、3、5
7	弹出	1、2、3	5
8	弹出	1、2	3
9	弹出	1	2
10	弹出		1

       接下来再分析弹出序列4、3、5、1、2。第一个弹出的数字4的情况和前面一样。把4弹出之后，3位于栈顶，可以直接弹出。接下来希望弹出的数字是5，由于5不是栈顶数字，到压栈序列里把没有压栈的数字压入辅助栈，直至遇到数字5。把数字5 压入栈之后，5就位于栈顶了，可以弹出。此时栈内有两个数字1和2，其中2位于栈顶。由于接下来需要弹出的数字是1，但1不在栈顶，我们需要从压栈序列中尚未压入栈的数字中去搜索这个数字。但此时压栈序列中所有数字都已经压入栈了。所以该序列不是序列 1、 2、 3、 4、 5对应的弹出序列。表2总结了这个例子中压栈和弹出的过程。

表2 一个压入顺序为1、2、3、4、5的栈没有一个弹出序列为为4、3、5、1、2

步骤	操作	栈	弹出数字
1	压入1	1
2	压入2	1、2
3	压入3	1、2、3
4	压入4	1、2、3、4
5	弹出	1、2、3	4
6	弹出	1、2	3
7	压入5	1、2、5
8	弹出	1、2	5
下一个弹出的是1，但1不在栈顶，压栈序列的数字都已入栈。操作无法继续

         总结上述入栈、 出栈的过程， 我们可以找到判断一个序列是不是栈的弹出序列的规律：如果下一个弹出的数字刚好是栈顶数字， 那么直接弹出。如果下一个弹出的数字不在栈顶， 我们把压栈序列中还没有入栈的数字压入辅助栈， 直到把下个需要弹出的数字压入栈顶为止。 如果所有的数字都压入栈了仍然没有找到下一个弹出的数字，那么该序列不可能是一个弹出序列。

已经AC的Python代码：

方法一：

class Solution:

    def isPopOrder(self, pushV, popV):
        length1 = len(pushV)
        length2 = len(popV)

        if length1 != length2 or length1 == 0:
            return False

        pNextPush = 0
        pNextPop = 0

        # 辅助栈
        stack = []

        while True:
            number = pushV[pNextPush]
            # 入栈
            stack.append(number)

            # 当入栈的元素与popV的当前元素相同，则出栈，并且pNextPop指向下一个
            while stack and stack[-1] == popV[pNextPop]:
                stack.pop()
                pNextPop += 1

            # 当pNextPush指向最后一个元素时，模拟出入栈已经结束，如果popV表示正确的出栈顺序，那么stack应该为空
            if pNextPush == length1 - 1:
                if stack:
                    return False
                else:
                    return True
            pNextPush += 1


if __name__ == "__main__":
    sol = Solution()
    pushV = [1, 2, 3, 4, 5]
    popV = [4, 5, 3, 2, 1]
#     popV = [4, 3, 5 ,1, 2]
    print(sol.isPopOrder(pushV, popV))

方法二： 

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

    def isPopOrder(self, pushV, popV):
        stack = []
        while popV:
            # 如果pushV不空，且与popV头元素都相同，则出栈
            if pushV and pushV[0] == popV[0]:
                pushV.pop(0)
                popV.pop(0)
            # 如果不满足前面的条件，判断stack是否为空，不为空则判断stack[-1]与popV[0]是否相等，相等则出栈。
            elif stack and stack[-1] == popV[0]:
                popV.pop(0)
                stack.pop(-1)
            # 如果pushV不空则，stack入栈
            elif pushV:
                stack.append(pushV.pop(0))
            # 最后说明pushV为空，且stack[-1]与popV[0]不相同，则出栈序列有误，返回False
            else:
                return False
        return True


if __name__ == "__main__":
    sol = Solution()
    pushV = [1, 2, 3, 4, 5]
    # popV = [4, 5, 3, 2, 1]
    popV = [4, 3, 5 ,1, 2]
    print(sol.isPopOrder(pushV, popV))

注：本文代码GitHub地址为 https://github.com/Microstrong0305/Screenshot-to-Code/tree/master/Data%20Structure%20and%20Algorithm

Reference：

【1】《剑指offer》何海涛著。

【2】https://blog.csdn.net/qq_34364995/article/details/81477676

【3】https://blog.csdn.net/l_vip/article/details/79160506