两种思路,以出栈元素为基准vs以入栈元素为基准,方法2明显实现起来更简单
方法1
迭代弹出栈的每一个元素:
新建一个栈,往里面压元素,直到压到和下一个弹出元素相同的元素,然后出栈
方法2
迭代压入栈的每一个元素:
新建一个栈,往里面压元素,每压入一个元素,就检查是否是需要弹出的,如果是则出栈
class Solution(object):
def isPopOrder(self, pushV, popV):
"""
:type pushV: list[int]
:type popV: list[int]
:rtype: bool
"""
arr, brr = pushV, popV
if len(arr) != len(brr): return False
if arr == brr == []: return True
bi = 0
crr = []
for a in arr:
crr.append(a)
while crr and crr[-1] == brr[bi]:
crr.pop()
bi += 1
return bi == len(brr)
crr = []
ai = bi = 0
alen, blen = len(arr), len(brr)
while True:
while ((not crr) and ai < alen) or (crr and crr[-1] != brr[bi] and ai < alen):
crr.append(arr[ai])
ai += 1
if crr and crr[-1] == brr[bi]:
crr.pop()
bi += 1
else:
break
return bi == len(brr)