文章目录
题目
标题和出处
标题：最大连续 1 的个数
难度
3 级
题目描述
要求
给定一个二进制数组 nums \texttt{nums} nums，返回数组中的最大连续 1 \texttt{1} 1 的个数。
示例
示例 1：
输入：
[1,1,0,1,1,1]
\texttt{[1,1,0,1,1,1]}
[1,1,0,1,1,1]
输出：
3
\texttt{3}
3
解释：开头的两位和最后的三位都是连续
1
\texttt{1}
1，所以最大连续
1
\texttt{1}
1 的个数是
3
\texttt{3}
3。
示例 2：
输入：
[1,0,1,1,0,1]
\texttt{[1,0,1,1,0,1]}
[1,0,1,1,0,1]
输出：
2
\texttt{2}
2
数据范围
- 1 ≤ nums.length ≤ 10 5 \texttt{1} \le \texttt{nums.length} \le \texttt{10}^\texttt{5} 1≤nums.length≤105
- nums[i] \texttt{nums[i]} nums[i] 是 0 \texttt{0} 0 或 1 \texttt{1} 1
解法
思路和算法
可以通过遍历数组得到最大连续的 1 1 1 的个数，对于每个下标，根据该下标处的元素计算以该下标结尾的最大连续 1 1 1 的个数。
如果数组中的一个元素是 0 0 0，则以该元素所在下标结尾的元素中一定有不是 1 1 1 的元素，因此对应的最大连续 1 1 1 的个数是 0 0 0。
如果数组中的一个元素是 1 1 1，则考虑以前一个元素结尾的最大连续 1 1 1 的个数。假设以前一个元素结尾的最大连续 1 1 1 的个数是 x x x，当前元素是 1 1 1，则以当前元素结尾的最大连续 1 1 1 的个数是 x + 1 x+1 x+1。如果当前元素是数组的第一个元素（即位于下标 0 0 0），或者前一个元素是 0 0 0，则对应 x = 0 x=0 x=0，该计算方法同样适用。
基于上述分析，可以得到如下解法：遍历数组，在遍历过程中，对于每个下标都记录以该下标结尾的最大连续 1 1 1 的个数，同时维护整个数组的最大连续 1 1 1 的个数。遍历结束之后，即可得到整个数组的最大连续 1 1 1 的个数。
代码
class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int count = 0, maxCount = 0;
int length = nums.length;
for (int i = 0; i < length; i++) {
count = nums[i] == 0 ? 0 : count + 1;
maxCount = Math.max(maxCount, count);
}
return maxCount;
}
}
复杂度分析
-
时间复杂度： O ( n ) O(n) O(n)，其中 n n n 是数组 nums \textit{nums} nums 的长度。需要遍历数组 nums \textit{nums} nums 一次，遍历过程中维护最大连续 1 1 1 的个数。
-
空间复杂度： O ( 1 ) O(1) O(1)。