最大连续数

Question

我正在练习两指针技术来解决最大连续数 - 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。

然而，很难找到指向第一个 One 的慢速指向。[0, 0, 0, 1, 1, 1, 1],

作为一个组合提案，重新定义慢速到达非一数组，而快速到达另一个非一数组。使用关系：长度=快-慢+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]

我多次尝试和调试将slow定义为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 code 测试，但没有设置任何速度记录。