跳到主要内容

485. Max Consecutive Ones (最大连续 1 的个数)

题目链接： 485. Max Consecutive Ones

Difficulty: Easy

Topics: Array

Question​

Given a binary array numnum, return the maximum number of consecutive1*'s in the array*.

Example 1:

Input: nums = [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.

Example 2:

Input: nums = [1, 0, 1, 1, 0, 1]
Output: 2

Constraints:

  • 1≤nums.length≤1051 \leq nums.length \leq 10^5
  • nums[i]nums[i] is either 00 or 11

解题思路​

方法1:​

思路​

我们需要找最大的连续是1的个数，那么我们就需要找到所有连续的1分别有多少，并且留下最多的是多少个。

  • 首先初始化最大的计数和当前计数均为0
  • for循环遍历，检测当前值为1的话就对current_countcurrent\_count进行+1+1的更新
    • 否则就看current_countcurrent\_count和我们记录的max_countmax\_count，保留最大计数，并重置current_countcurrent\_count的值为0
  • 最后返回的时候也要返回current_countcurrent\_count和max_countmax\_count里最大的那个，因为最长的那段1可能直接到结尾，在for循环里就没有走到过elseelse的部分。

代码​

class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        max_count = current_count = 0
        for num in nums:
            if num == 1:
                current_count += 1
            else:
                max_count = max(current_count, max_count)
                current_count = 0
        return max(current_count, max_count)

时间复杂度​

  • 这种方法的时间复杂度出现在for循环中，只进行了一遍遍历，也就是O(n)O(n)。