题解 | #栈的压入、弹出序列#
栈的压入、弹出序列
http://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106
# -*- coding:utf-8 -*- class Solution: def IsPopOrder(self, pushV, popV): # write code here i = 0 j = 0 while pushV: if pushV[i] != popV[j]: i += 1 if i>=len(pushV): return False else: print(pushV, i) pushV.pop(i) j += 1 i -= 1 return True
双指针解法:
i是pushV的指针,j是popV的指针。两指针都从头开始,当pushV[i]等于popV[j]时,pushV有两种选择:1)继续弹出,弹出的就是pushV的第i-1个元素;2)压入pushV的第i+1个元素。因此只需判断pushV第i-1个元素与popV的第j+1个元素是否相等即可得到是弹出还是压入。若是压入则i将从i-1的位置继续往下走;若是弹出则i从i-1的位置持续往前走。