题目描述

给定一个二进制数组 nums，计算其中最大连续 1 的个数。

示例 1：

1
2
3
输入：nums = [1,1,0,1,1,1]
输出：3
解释：开头的两位和末尾的三位都是连续 1，所以最大连续 1 的个数是 3。

示例 2：

1
2
输入：nums = [1,0,1,1,0,1]
输出：2

解题思路

本题要求找出二进制数组中最长的一段连续 1 的长度。核心思想是遍历数组并维护两个变量：当前连续 1 的长度（pre_sum）和全局最大连续 1 的长度（max_sum）。

算法分析步骤：

  1. 初始化 pre_sum = 0（当前连续 1 的长度）和 max_sum = 0（全局最大值）。
  2. 遍历数组中的每个元素 nums[i]：
    • 尝试将当前元素累加到 pre_sum 上，计算结果 res = pre_sum + nums[i]。
    • 关键判断： 如果 res == pre_sum，说明 nums[i] == 0（累加后值不变，即遇到 0）。此时：
      • 用当前的 pre_sum（即上一个连续 1 段的长度）更新 max_sum。
      • 将 pre_sum 重置为 0，开始下一段计数。
    • 否则（res > pre_sum），说明 nums[i] == 1：
      • 将 pre_sum 加 1，继续累加当前连续 1 的长度。
  3. 遍历结束后，最后一段连续 1 的长度可能还未与 max_sum 比较（如果数组以 1 结尾），因此返回 max(max_sum, pre_sum)。

为什么这个判断方式有效？ 因为二进制数组中元素只有 0 和 1。pre_sum + 1 > pre_sum（遇到 1），而 pre_sum + 0 == pre_sum（遇到 0）。利用累加后是否变化来区分遇 0 和遇 1，同时用 pre_sum 记录当前连续 1 的计数。遇到 0 时结算一段，重置计数器；遇到 1 时继续累加。

复杂度分析

  • 时间复杂度： O(n)，其中 n 为数组长度。只需要一次遍历即可完成计算。
  • 空间复杂度： O(1)，只使用了常数个额外变量（pre_sum、max_sum、res），不随输入规模增长。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from typing import List


class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        pre_sum = 0
        max_sum = 0
        for i in range(len(nums)):
            res = pre_sum + nums[i]
            if res == pre_sum:
                max_sum = max(max_sum, res)
                pre_sum = 0
            else:
                pre_sum += nums[i]
        return max(max_sum, pre_sum)