最大连续1的个数

Question

我正在练习双指针技巧来解决最大连续1的问题 - LeetCode

Given a binary array, find the maximum number of consecutive 1s in this array.

Example 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.

Note:

• The input array will only contain 0 and 1.
• The length of input array is a positive integer and will not exceed 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)

这个解决方案的问题在于它不是一个像快慢指针那样得体的解决方案。(它没有明确的慢指针)

使用慢指针的直觉想法是使用慢指针记住连续1的起始索引，当快指针到达非1时，关系为 长度=快指针-慢指针。

然而，很难将慢指针定位到第一个1。例如[0, 0, 0, 1, 1, 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子数组的第一个索引，但未获得期望的结果。

您能否给出任何解决方案的提示？

- Alice

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 

这个通过了LeetCode测试，但没有创造任何速度记录。

- Mark

Answer 2

您可以尝试以下解决方案。基本上，您要跟踪计数，直到达到0，然后返回maxCount。

  public int findMaxConsecutiveOnes(int[] nums) {
    int currentCount=0;
    int maxCount = 0;
    for(int i=0;i<nums.length;i++){
        if(nums[i]==1){
            currentCount++;
            if(currentCount>maxCount){
                maxCount=currentCount;
            }
        }
        else{
            currentCount=0;
        }

    }
    return maxCount;
}

- Rohan Paul

Answer 3

你也可以像下面这样解决这个程序（一行解决方案）：

class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        return len(max("".join(map(str, nums)).split("0")))

希望这个解决方案对你有所帮助 :)

- sourab maity

Answer 4

这是我解决问题的方法：

class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        c = 0
        r = 0
        for i,v in enumerate(nums):
            if v == 0:
                c = 0
            else:
                c +=1
                r = max(r,c)
        return r

这是我的时间和空间分析结果：

- Alex Maina