如何处理 leetcode 的 487. Max Consecutive Ones II 的流式案例？

Question

问题问：

Given a binary array nums, return the maximum number of consecutive 1's in the array if you can flip at most one 0.

当我可以看到此问题的先前值时，我能够使用滑动 window 解决方案。

但是，我不知道如何解决流式传输的后续问题。

Follow up: What if the input numbers come in one by one as an infinite stream? In other words, you can't store all numbers coming from the stream as it's too large to hold in memory. Could you solve it efficiently?

我认为我无法像在滑动 window 中那样访问以前的值。我是否必须记录零出现的位置？

我能够使用代码来解决更简单的问题 Max Consecutive Ones I 滑动 window 所以我认为滑动 window 代码可以扩展到流式传输案例。

# sliding window approach
from typing import List
class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        longestSequence = 0
        left = 0
        right = 0
        maxZeroes = 1   # allows us to modify our code in 1 place if we need more than 1 zero next time
        numZeroes = 0

        for right in range(len(nums)):
            if nums[right] == 0:
                numZeroes += 1
            
            while numZeroes == maxZeroes + 1:
                if nums[left] == 0:
                    numZeroes -= 1
                left += 1


            longestSequence = max(longestSequence, right - left + 1) 

        return longestSequence

Answer 1

您可以计算连续数字的数量，再计算连续数字的数量，最多包括一个零，然后计算其中任何一个的最大值运行。无需跟踪 positions:

    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        countwithzero = 0
        countones = 0
        maxcount = 0
        for bit in nums:
            if bit:
                countones += 1
                countwithzero += 1
            else:
                countwithzero = countones + 1
                countones = 0
            maxcount = max(maxcount, countwithzero, countones)

        return maxcount

如何处理 leetcode 的 487. Max Consecutive Ones II 的流式案例？

How does one handle the streaming case for leetcode's 487. Max Consecutive Ones II?

python

algorithm