最高连续一次

Question

我正在练习两个技巧来解决Max Consecutive Ones - LeetCode

给定二进制数组，找到此数组中连续1的最大数量。

例1：

Input: [1,1,0,1,1,1]
Output: 3
Explanation: The first two digits or the last three digits are consecutive 1s.
 The maximum number of consecutive 1s is 3.

注意：

• 输入数组只包含0和1。
• 输入数组的长度是一个正整数，不会超过10,000

该解决方案使用Kadane算法

class Solution:
    def findMaxConsecutiveOnes(self, nums: "List[int]") -> int:

        loc_max = glo_max = 0
        for i in range(len(nums)):
            if nums[i] == 1: 
                loc_max += 1
            elif nums[i] != 1:
                glo_max = max(glo_max, loc_max)
                loc_max = 0  
        #in case of the corner case [.....,1 ,1, 1]         
        return max(glo_max, loc_max)

该解决方案的问题在于它不是一个具有慢速和快速指针的合适的双指针解决方案。（它没有明确的慢速指针）

使用慢指针的一个直观想法是采用慢指针来记住连续的指针的起始索引，当快速指针到达非指针时，关系是length= fast - slow。

但是，很难找到慢速指向第一个。 [0, 0, 0, 1, 1, 1, 1]，

作为一个包含的提议，当快速到达另一个非一个时，重新定义一个数组的前向非一个慢。使用关系：length = fast -slow + 1

class Solution:
    def findMaxConsecutiveOnes(self, nums: "List[int]") -> int:
        """
        #1Sort####
        ##2Strategy######
        CP: two pointers
        RU: res  = fast - slow 
        """
       ###3Solve######
        slow, fast, glo_max = 0, 0, 0
        for fast in range(len(nums)):
            if nums[fast] != 1: #stop
                loc_max = fast -slow + 1
                glo_max = max(glo_max, loc_max)
                slow = fast 
        return max(loc_max, glo_max)
        ####4Check#########################
        #[0, 0,1, 0, 1, 1]

我多次尝试和调试将慢速定义为Ones子阵列的第一个索引，但未获得所需的结果。

你能不能给出解决方案的任何提示。

Answer 1

我认为你非常接近，这只是一个真正关注的问题，当索引相对于你计算长度时更新。还有像[1]这样的棘手案例如果不正确就会失败。

我发现使用while循环更容易实现这一点，因此我可以明确指出索引的更新位置。这是一种有效的方法：

 def findMaxConsecutiveOnes(nums):
        slow, fast, glo_max, loc_max = 0, 0, 0, 0
        while fast < len(nums):
            if nums[fast] == 0:
                loc_max = fast - slow  
                glo_max = max(glo_max, loc_max)
                slow = fast + 1      # need to add one more because we haven't incremented fast yet

            fast += 1
        loc_max = fast - slow        # end check for cases that end with 1
        return max(loc_max, glo_max)

findMaxConsecutiveOnes([1])    # 1 
findMaxConsecutiveOnes([1, 1]) # 2
findMaxConsecutiveOnes([0, 1]) # 1
findMaxConsecutiveOnes([0, 1, 1, 0, 0, 1, 1, 1, 0]) # 3 

这通过了leet代码测试，但没有设置任何速度记录。