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

栈的压入、弹出序列

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的位置持续往前走。
全部评论
pop(i)?
点赞 回复
分享
发布于 2022-04-05 01:46

相关推荐

2 收藏 评论
分享
牛客网
牛客企业服务