LeetCode 485. 最大连续 1 的个数
题目描述
题意分析
数组中只有 $0$ 和 $1$，求最长连续一段 $1$ 的长度。连续段必须占据相邻位置，遇到 $0$ 就被切断，不能通过跳过、删除或翻转 $0$ 把两段合并。
解法：线性扫描
核心思路
[!blue]
扫描过程中，只有当前末尾这段连续的 $1$ 还可能向后延长；已经被 $0$ 截断的段不会参与后续新段，只需保留它们贡献过的最大长度。因此用两个变量就能记录全部必要信息：
cur是以当前元素结尾的连续 $1$ 的长度，best是已扫描前缀中出现过的最大长度。
- 当前元素为 $1$：它可以接在上一位置结尾的连续段后面，所以执行
cur++；再用新的cur更新best。若上一项是 $0$，此前的cur为 $0$，这一步就自然开始长度为 $1$ 的新段。- 当前元素为 $0$：不存在以它结尾的全 $1$ 片段，令
cur = 0。历史最长段仍然有效，best不变。初始还没有读取任何元素，两个长度都为 $0$。每处理一项，上述更新都保持两个变量的含义；遍历结束后，
best已经覆盖所有可能的连续段，就是答案。每次遇到 $1$ 都立即更新最大值，因此最后一段即使没有被 $0$ 结尾，也不会漏算。全零数组的答案保持为 $0$，全一数组则会不断延长到整个数组长度，无需额外分支。
解题步骤
- 初始化当前长度与最大长度为零。
- 遇到一，先延长再更新最大值。
- 遇到零，当前长度归零。
- 返回全局最大值。
代码实现
class Solution {
// 遇到 1 则计数加一，遇到 0 则重置为 0。
public int findMaxConsecutiveOnes(int[] nums) {
int cur = 0;
int best = 0;
for (int num : nums) {
if (num == 1) {
cur++;
// 延长后立即刷新，末尾没有零也不会漏记最长段
best = Math.max(best, cur);
} else {
// 零切断当前连续段，历史最大值不清空
cur = 0;
}
}
return best;
}
}
func findMaxConsecutiveOnes(nums []int) int {
// 遇到 1 则计数加一，遇到 0 则重置为 0。
cur := 0
best := 0
for _, v := range nums {
if v == 1 {
cur++
// 延长后立即刷新，末尾没有零也不会漏记最长段
if cur > best {
best = cur
}
} else {
// 零切断当前连续段，历史最大值不清空
cur = 0
}
}
return best
}
复杂度分析
- 时间复杂度：$O(n)$，只扫描一次。
- 空间复杂度：$O(1)$，两个计数变量。
关键点总结
[!green]
- 当前末端长度与全局最长长度是两个状态。
- 遇到零后不能继承前一段长度。
易错点总结
[!yellow]
- 遇到零只把
cur减一，会让已经断开的前一段残留到后面的计数中；必须归零。- 只在遇到零时更新答案，会漏掉全一或末尾最长段。
- 返回 cur 会丢掉前面更长、但已经结束的段。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1004. 最大连续1的个数 III | 中等 | 允许翻转k个0后，连续1统计扩展成零数不超过k的滑动窗口。 |
| 1493. 删掉一个元素以后全为 1 的最长子数组 | 中等 | 原题必须删除一个位置，本题不做修改，只统计已有连续1段。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！