0485._Max_Consecutive_Ones.md

485. Max Consecutive Ones

难度: Easy

刷题内容

原题连接

• https://leetcode.com/problems/max-consecutive-ones/description/

内容描述

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

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(1)******

一行无敌，beats 82.12%

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

思路 2 - 时间复杂度: O(N)- 空间复杂度: O(1)******

每走一步都更新一下res，beats 39.33%

class Solution(object):
    def findMaxConsecutiveOnes(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res, cnt = 0, 0
        for i, num in enumerate(nums):
            cnt = cnt + 1 if num else 0
            res = max(res, cnt)
        return res

思路 3 - 时间复杂度: O(N)- 空间复杂度: O(1)******

双指针，走完连续的1之后才更新res，同时更新idx，beats 61.80%

class Solution(object):
    def findMaxConsecutiveOnes(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        l = r = res = 0
        while r < len(nums):
            while r < len(nums) and nums[r]: 
                r += 1
            res = max(res, r - l)
            r += 1
            l = r
        return res

思路 4 - 时间复杂度: O(N)- 空间复杂度: O(1)******

不为1的时候才更新res，beats 97.00%

class Solution(object):
    def findMaxConsecutiveOnes(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """  
        cnt, res = 0, 0
        for i in nums:
            if i == 1:
                cnt += 1
            else:
                res = max(res, cnt)
                cnt = 0
        return max(res, cnt)