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的索引减小为04.3 复杂度分析
- 时间复杂度：O(n)(需要计算的数组最长为n)
- 空间复杂度：O(1) (在原数组上操作，没用额外空间的使用，所以是常量的O(1))
京公网安备 11010502036488号