题解 | #栈的压入、弹出序列#
栈的压入、弹出序列
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的位置持续往前走。
投递思朗科技等公司10个岗位
