LeetCode 485. 最大连续 1 的个数
目录
题目描述
题意分析
给一个只含 0 和 1 的数组，求其中连续的 1 最长能有多长，返回这个长度。
关键词是「连续」，也就是要求这些 1 在下标上首尾相接、中间不能夹任何 0。这与「1 的总个数」完全不同，
[1,0,1,1]的答案是 2 而不是 3。读题时要先把这一点锁死。数组只有 0 和 1 两种取值，这个约束非常强：0 是唯一的分隔符。整个数组被 0 天然切成若干段全 1 的区间，问题等价于求这些区间里最长的那段。识别出「元素只有两类、其中一类做分隔符」这个结构，解法方向就基本定了。
题目不允许翻转或删除任何元素，这也是它比 487、1004、1493 简单的根本原因——那几道题允许把有限个 0 当成 1 用，必须维护一个可伸缩的窗口；本题不允许，窗口一旦遇到 0 就整段作废，无需回退。
数据规模是长度不超过 $10^5$，线性扫描绰绰有余，不需要任何预处理或额外结构。
边界上，题目保证数组非空，但要考虑全 0（答案 0）、全 1（答案是数组长度）、以及最长的一段恰好紧贴数组末尾这三种情况——最后一种是本题最容易漏掉的。
解法：线性扫描
核心思路
暴力做法是枚举所有子数组，检查每个子数组是否全为 1，取最长的。这是 $O(n^2)$ 甚至 $O(n^3)$ 的量级，在 $10^5$ 规模下不可行。
瓶颈在于反复重新检查了同一段数据。而观察到一个可以直接消掉这个开销的性质：从左往右扫描时，「以当前位置结尾的连续 1 的长度」只取决于前一个位置的同类信息。如果当前是 1，它等于前一个位置的值加一；如果当前是 0，它等于 0。这是一条极简的递推关系，只需要保存前一个值，不需要保存整个历史。
于是用一个变量
cur承担这个递推，另一个变量best记录扫描过程中cur达到过的最大值。循环不变量是：每处理完下标
i，cur恰好等于以nums[i]结尾的连续 1 的长度，best恰好等于前缀nums[0..i]中所有连续 1 段的最大长度。初始时前缀为空，两者都是 0；每一步按上面的递推更新cur，再用cur去刷新best，不变量得以维持。扫描结束时前缀就是整个数组，best就是答案。之所以「遇到 0 直接把
cur清零」是正确的，是因为任何跨越这个 0 的区间都不可能全为 1，前面积累的长度对后面的段没有任何参考价值，可以安全丢弃。这正是本题不需要滑动窗口的原因——窗口左边界永远直接跳到 0 的后面，不存在渐进收缩。
best的更新放在「遇到 1」的分支里即可，因为cur只可能在这个分支变大；放在循环末尾无条件更新同样正确，只是多做几次无用比较。这个选择也解释了为什么循环结束后不需要再补一次比较——最长段即使紧贴数组末尾，它的最后一个 1 也已经在循环内部刷新过best了。
解题步骤
- 初始化
cur = 0、best = 0：cur是「以当前位置结尾的连续 1 长度」，扫描开始前没有任何元素，所以是 0；best初值取 0 而不是Integer.MIN_VALUE，因为答案下界本来就是 0（全 0 数组的正确答案），这样全 0 用例无需特判。- 用增强 for 顺序遍历数组：本题只需要元素值、不需要下标，用
for (int num : nums)更简洁；顺序必须从左到右，因为递推方向是「依赖前一个位置」。- 遇到 1 时
cur++：把当前元素接到正在积累的这段后面，长度加一。- 紧接着
best = Math.max(best, cur)：必须在cur++之后立刻更新，这样每一段的峰值都能被捕获。放在这里而不是循环末尾，是因为cur只在这一支变大，遇到 0 那支只会变小，无需比较。- 遇到 0 时
cur = 0：直接清零而不是递减，因为这个 0 把前后彻底隔断，之前积累的长度对后续毫无用处。注意这里不能顺手更新best，也不需要——峰值早在上一个 1 处就记录过了。- 返回
best：循环内已经处理完所有位置，末尾无需补任何逻辑。以
nums = [1,1,0,1,1,1]走一遍。初始：
cur = 0、best = 0。下标 0（值 1）：
cur = 1，best = max(0,1) = 1。以下标 0 结尾的连续 1 长度确实是 1。下标 1（值 1）：
cur = 2，best = max(1,2) = 2。下标 2（值 0）：
cur = 0，best保持 2。此处清零切断了前后两段。下标 3（值 1）：
cur = 1，best = max(2,1) = 2。新段刚开始，还没超过历史最大值。下标 4（值 1）：
cur = 2，best = 2。下标 5（值 1）：
cur = 3，best = max(2,3) = 3。循环结束，返回 3。注意最长的这一段紧贴数组末尾，但因为
best是在每个 1 处即时更新的，末尾不需要补充任何比较就已经拿到了正确答案。再看两个极端用例。
nums = [0,0]：两轮都走cur = 0分支，best始终是初值 0，返回 0，正确。nums = [1]：一轮后cur = 1、best = 1，返回 1，正确。
代码实现
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)$，其中 $n$ 是数组长度。只扫描一趟，每个元素做一次判断和至多一次比较，全是常数操作，没有任何回退。
- 空间复杂度：$O(1)$，只用了
cur和best两个整型变量，与数组长度无关。不需要前缀和数组，也不需要记录每段的起止位置。
关键点总结
- 「最长连续满足某性质的子数组」这类问题，先问一句违反性质的元素能否被容忍：不能容忍就是本题的清零式扫描 $O(1)$ 空间；能容忍 $k$ 个就升级成滑动窗口。这个判断能瞬间把 485、487、1004 三题区分开。
- 状态定义写成「以当前位置结尾的最优值」，往往能把二维的子数组枚举压成一维递推；最大子数组和、最长递增子序列的 $O(n^2)$ 解法都是同一个思路。
- 遇到分隔符直接清零而非递减，本质是因为跨越分隔符的答案一定不合法，历史积累毫无参考价值——能论证「可以安全丢弃」是这类贪心式扫描的正确性来源。
- 答案更新的位置要与「什么时候可能变大」对齐：
cur只在遇到 1 时增大，所以只在那一支刷新best即可，循环结束后无需补刀。想不清楚时，把更新无条件放在循环末尾是最保险的写法。best初值取答案的自然下界（这里是 0），能让全 0 这种极端输入自然落进主逻辑，比事后特判更干净。
易错点总结
- 把
cur = 0写成cur--：[1,1,0,1]时下标 2 处cur从 2 减到 1，下标 3 又加回 2，返回 2 虽然碰巧对，但换成[1,1,1,0,1]就会得到 3 之后再涨到 3，把被 0 隔开的两段错误地部分拼接了。- 在遇到 0 的分支里忘记重置：
[1,0,1]会一路累加成cur = 2，返回 2，而正确答案是 1——这等于把题目从「最长连续 1」做成了「1 的总数」。- 只在遇到 0 时才更新
best：[1,1,1]全程不进 0 分支，best停留在初值 0，返回 0 而不是 3；最长段紧贴数组末尾时必然翻车。best初值设成nums[0]或 1：[0,0,0]会返回 1 或 0 之外的错误值，全 0 数组的正确答案必须是 0。best = Math.max(best, cur)写在cur++之前：[1]会用旧的cur = 0去比较，返回 0 而不是 1，整体结果永远比正确答案少 1。- 判断写成
if (num != 0)（或num > 0）：本题恰好只有 0 和 1 所以看不出问题，但一旦被面试官改成含有 2 的数组，[1,2,1]会返回 3，而 2 本不该被计入。- 误以为要统计 1 的总个数：
[1,0,1,1]会返回 3，正确答案是 2；这是读题层面的错误，比代码错误更致命。- 用双重循环枚举所有子数组再检查：逻辑虽对，但 $10^5$ 长度下 $O(n^2)$ 是 $10^{10}$ 次操作，必然超时。
- 借助滑动窗口并允许窗口内含 0：本题不允许任何翻转，窗口一旦含 0 就非法，写成 1004 的模板并把
k设成 0 虽然能过，但多出无谓的左指针收缩逻辑，面试中会被认为没看清题目的简化条件。- 返回
cur而不是best：[1,1,0]结束时cur已被清零，返回 0 而不是 2；只有当最长段恰好在末尾时才碰巧正确。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 487. 最大连续1的个数 II | 中等 | 允许翻转一个 0，清零式扫描升级为记录「上一个 0 位置」的双变量法 |
| 1004. 最大连续1的个数 III | 中等 | 允许翻转 k 个 0，必须用滑动窗口按 0 的个数收缩左边界 |
| 1493. 删掉一个元素以后全为 1 的最长子数组 | 中等 | 必须删掉恰好一个元素，答案要在窗口长度上再减一且需处理全 1 特例 |
| 面试题 05.03. 翻转数位 | 简单 | 与 487 同构，但输入是一个整数，需先按位取出再扫描 |
| 1446. 连续字符 | 简单 | 分隔符从「0」变成「与前一个字符不同」，递推条件改成比较相邻元素 |
| 674. 最长连续递增序列 | 简单 | 分隔条件是 nums[i] <= nums[i-1]，同样的清零式扫描骨架 |
| 53. 最大子数组和 | 中等 | 同为「以当前位置结尾」的递推，但重置条件从遇 0 变成前缀和为负 |
| 424. 替换后的最长重复字符 | 中等 | 字符不止两类，需在窗口内维护各字符计数并用最大频次判断可行性 |
| 3. 无重复字符的最长子串 | 中等 | 违规元素的位置不固定，左指针需跳到重复字符上次出现处的下一位 |
| 128. 最长连续序列 | 中等 | 「连续」指数值连续而非下标连续，需借哈希集合从每段起点向后延伸 |