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

1. 解题思路：辅助栈

首先我们创建一个辅助栈stack，并初始化。然后遍历pushV，依次把元素压入该辅助栈中：

同时也比较辅助栈的栈顶元素与popV的初始元素，当发现两元素相等的时候：

就停止压入，然后弹出该栈顶元素：

此时辅助栈中就只有三个元素，因为pushV还有元素，所以接着添加到辅助栈中，再同popV的下一个元素比较：

发现又是相等的两元素，所以继续弹出stack中的栈顶元素；后面就一直重复这个过程。直到最后辅助栈清空！而popV的 j 值刚好等于 popV的长度，此时这个popV的顺序就是压入栈的弹出顺序！！！

2. 核心代码

# -*- coding:utf-8 -*-
class Solution:
    def IsPopOrder(self, pushV, popV):
        j = 0        
        stack = []    #初始化一个辅助栈stack
        for x in pushV:     #把压入序列中的元素依次添加到辅助栈中
            stack.append(x)
            while stack and stack[-1] == popV[j]: #如果辅助栈的 栈顶元素就等于弹出栈的j 位对应元素
                stack.pop()                                         #弹出辅助栈该元素
                j += 1                                              #j 累加

        return j == len(popV)                                       #最后直到j等于弹出序列长度结束该循环

3. 复杂度分析

• 时间复杂度：O(n)(因为辅助栈的最差就是遍历整个压入栈长度，花费时间是n；同理空间复杂度也是n）
• 空间复杂度：O(n)

PS:
示例1 之所以会返回False，就是因为辅助栈的栈顶为 2 这个元素的时候，它与 popV的对应元素不相等！！！所以它不是该栈的弹出顺序。

输入：
[1,2,3,4,5],[4,3,5,1,2]
返回值：false

------------------------------------------------我是解法二的分割线-------------------------------------------------

4.解法二

4.1 思路

其实我们还可以不用辅助栈，直接在pushV数组上进行操作（仔细看上面的分析就可以知道辅助栈跟 pushV是一样的），这样可以把空间复杂度优化为只需要O(1)。

• 当pushV[i] != popV[0]元素，表示还没匹配到待弹出元素；继续i = i + 1压入元素；
• 当push[i] == popV[0]时，即匹配上弹出元素，并i = i - 1让它始终指向pushV的顶部元素；同时popV也要更新到下一个元素j = j + 1，使其成为新的popV[0]。最后直到pushV 和popV都为空即匹配结束。

4.2 核心代码

# -*- coding:utf-8 -*-
class Solution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        #不用辅助栈，直接把pushV当作stack来处理
        i = j = 0
        for x in pushV:
            pushV[i] = x                                     #直接把pushV当作压入栈
            while i >= 0 and pushV[i] == popV[j]:            #当pushV的当前元素等于popV弹出列的顶部元素
                i, j = i - 1, j + 1                          #分别更新栈顶元素
            i += 1                                           #否则继续往pushV压入栈中添加元素
        return i == 0                                         #直到pushV的索引减小为0

4.3 复杂度分析

• 时间复杂度：O(n)(需要计算的数组最长为n)
• 空间复杂度：O(1) (在原数组上操作，没用额外空间的使用，所以是常量的O(1))