LeetCode 487. 最大连续1的个数 II

约 9 分钟
文章信息 2 个分类 5 个标签
分类
LeetCode 中等
标签
数组 动态规划 滑动窗口 滑动窗口经典题 最大连续 1 问题
目录

题目描述

✅ 487. 最大连续1的个数 II

image-20250420034917448

题意分析

题目目标：给一个只含 0 和 1 的数组，最多可以把一个 0 翻成 1，问翻转之后最长的连续 1 有多长。

核心约束：「最多翻一个 0」等价于「找一段最长的子数组，使得其中 0 的个数不超过 1」——这是全题唯一需要完成的转译。注意是「最多」不是「恰好」，全 1 数组不需要翻也合法。另外题目的进阶版本会追加一句「如果输入是无法一次性载入内存的流呢」，这提示解法必须只依赖一次正向扫描、且不回头访问任意位置。

边界处理：数组可能全是 1（答案是整个长度）、全是 0（答案是 1，翻掉其中一个）、长度为 1（答案是 1）；0 的个数为 0 时不能因为「没得翻」而返回 0。

实现取舍：可以按「以 $i$ 结尾、已用 $j$ 次翻转」建二维递推，也可以把它压成一个只增不减的窗口。两者是同一个东西的两种写法，后者代码只有五行，但需要额外解释「为什么最后返回 n - l」。

解法：动态规划递推

核心思路

暴力做法是枚举把哪个 0 翻掉，翻完之后再扫一遍求最长连续 1，$O(n^2)$。瓶颈在于每次翻转之后都要从头重算，而实际上翻掉一个 0 只影响它左右两段连续 1 的拼接。

先写出规范的递推，把状态定义钉死：设 f[i][0] 表示以下标 $i$ 结尾、一次翻转都没用的最长合法段长度，f[i][1] 表示以下标 $i$ 结尾、已经用掉一次翻转的最长合法段长度。转移是：nums[i] == 1 时两种状态都可以由前一位直接延长，f[i][0] = f[i-1][0] + 1、f[i][1] = f[i-1][1] + 1；nums[i] == 0 时，不翻就断了所以 f[i][0] = 0，翻掉它则必须由「此前没用过翻转」的状态接上，f[i][1] = f[i-1][0] + 1。答案是所有 f[i][1] 与 f[i][0] 的最大值。这个递推 $O(n)$ 时间、$O(1)$ 滚动空间，已经足够。

再观察一层。上面这个递推的实质是「维护一个 0 的个数不超过 1 的后缀」，也就是一个左端点单调右移的窗口。既然如此，可以直接用窗口来实现，而且用的是「只增不减」的窗口写法：窗口的长度一旦达到过某个值就永远不再缩短——每读入一个新元素窗口右端加一，只有当窗口内 0 的个数超标时左端才跟着加一，此时长度保持不变；不超标时长度加一。

于是不变量是：扫描到任意时刻，窗口长度 = 到目前为止见过的最长合法段长度，且左端点 l 只增不减。因为窗口从不收缩，最终窗口长度就是全局最优，而扫描结束时右端点恰好是 $n$，所以答案 = $n - l$，连 max 都不用维护。代码里用 cnt 记录窗口内 0 的个数，x ^ 1 是「0 记 1、1 记 0」的等价写法，比写 if 更短。

需要强调的是：这个写法中 cnt 在窗口滑动之后可能仍然大于 1（因为左端只移了一格，而移出去的恰好是个 1）。这不是 bug——窗口此刻确实非法，但它的长度等于历史最优，后续如果出现更好的位置，窗口会重新变回合法并继续增长。理解这一点是读懂这五行代码的关键。

解题步骤

第一步：l = 0、cnt = 0，l 是窗口左端点，cnt 是窗口内 0 的个数。 为什么不需要显式的 r：用 for-each 顺序遍历，当前元素天然就是右端点，窗口是 [l, 当前下标]。

第二步：每读入一个元素 x，执行 cnt += x ^ 1。 为什么用异或：x 只可能是 0 或 1，x ^ 1 把 0 映射成 1、把 1 映射成 0，正好是「这个元素是不是 0」的指示值，一行完成计数。

第三步：若 cnt > 1，执行 cnt -= nums[l++] ^ 1。 为什么阈值是 1：题目只允许翻一个 0，窗口内 0 的个数上限就是 1。为什么左端只移一格而不是 while 循环移到合法：这就是「不缩小窗口」的核心——右端每次进一格、左端最多出一格，窗口长度只会持平或增长，绝不缩短，从而始终记录着历史最大值。

第四步：扫描结束后返回 nums.length - l。 为什么这个差就是答案：窗口长度 = 右端点数量 $n$ 减去左端点 l，而由第三步的不变量，这个长度恰好等于历史上出现过的最长合法窗口。

以 nums = [1, 0, 1, 1, 0] 走一遍：初始 l = 0、cnt = 0。

读入下标 0 的 1：cnt += 1 ^ 1 = 0，cnt 仍为 0，不超标，窗口是 [0, 0]，长度 1。

读入下标 1 的 0：cnt += 0 ^ 1 = 1，cnt = 1，不超标（正好用掉唯一一次翻转），窗口是 [0, 1]，长度 2。

读入下标 2 的 1：cnt 不变仍为 1，窗口 [0, 2]，长度 3。

读入下标 3 的 1：cnt 仍为 1，窗口 [0, 3]，长度 4。此时窗口内容是 1,0,1,1，翻掉那个 0 得到 4 个连续 1，这就是答案。

读入下标 4 的 0：cnt 变成 2，超标。执行 cnt -= nums[0] ^ 1，nums[0] = 1 所以减去的是 0，cnt 仍为 2，l 变成 1。注意这里出现了上文说的现象——窗口 [1, 4] 的内容是 0,1,1,0，含两个 0，当前非法，但长度仍是 4，等于历史最优，不影响正确性。

扫描结束，返回 5 - 1 = 4，与期望一致。

再以 nums = [1, 0, 1, 1, 0, 1] 走一遍尾部：前五步同上，结束时 l = 1、cnt = 2。读入下标 5 的 1：cnt += 0 仍为 2，超标，执行 cnt -= nums[1] ^ 1，nums[1] = 0 所以减去 1，cnt 变成 1，l 变成 2。窗口 [2, 5] 内容是 1,1,0,1，恰好一个 0，重新合法，长度仍是 4。返回 6 - 2 = 4，正确——这一步演示了非法窗口如何自动恢复合法。

代码实现

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int l = 0, cnt = 0;
        for (int x : nums) {
            cnt += x ^ 1;
            if (cnt > 1) {
                cnt -= nums[l++] ^ 1;
            }
        }
        return nums.length - l;
    }
}

func findMaxConsecutiveOnes(nums []int) int {
    l, cnt := 0, 0
    for _, x := range nums {
        cnt += x ^ 1
        if cnt > 1 {
            cnt -= nums[l] ^ 1
            l++
        }
    }
    return len(nums) - l
}

复杂度分析

  • 时间复杂度：$O(n)$。凭什么：右端点由 for-each 推进恰好 $n$ 次，左端点 l 只增不减且不超过 $n$，两个指针的总移动次数是 $2n$，循环体内没有任何嵌套或回退。
  • 空间复杂度：$O(1)$。凭什么：只用了 l 和 cnt 两个整型变量，没有开辟与输入规模相关的数组；这也是它能直接处理数据流的原因——除了随机访问 nums[l] 需要保留最近的一段之外，不需要缓存整个输入。

关键点总结

  • 「最多修改 k 次」类问题的第一步永远是转译成「窗口内非法元素不超过 k 个」。 一旦完成这次翻译，题目就从构造问题变成了标准的窗口问题，k 的取值只影响一个常数。
  • 二维递推与滑动窗口经常是同一个算法的两种外衣。 先把 f[i][j] 写清楚能保证思路正确，再压成窗口能保证代码简洁，面试时按这个顺序讲最稳。
  • 「不缩小窗口」写法的核心是把 while 换成 if，用长度单调不减换掉显式的 max。 它要求你能说清楚「窗口有时非法但长度始终等于历史最优」，说不清就别用，老老实实写 while + max。
  • x ^ 1 是 0/1 数组上「取反计数」的惯用手法。 比 x == 0 ? 1 : 0 更短，前提是确认输入只有 0 和 1。
  • 答案用 n - l 表达，前提是窗口长度单调不减。 换成会收缩的窗口写法后这个式子立刻失效，必须改回显式 max。
  • 面试视角：先给 f[i][0]/f[i][1] 的递推证明自己会分析状态，再说「注意到它等价于一个至多含一个 0 的窗口」并写出窗口版本，最后主动回答进阶问题——「若输入是流，窗口写法只需缓存左端点之后的元素，无需载入全部数据」。面试官若追问「翻 k 个 0 呢」，把阈值 1 改成 k 即为 1004 题，这句话能顺势展示迁移能力。

易错点总结

  • 错误写法：把 if (cnt > 1) 写成 while (cnt > 1) 但仍返回 nums.length - l → 用例 [1,0,1,1,0]，读到下标 4 时 while 会一直移到 cnt <= 1，l 前进到 2，窗口收缩成 [2,4]，最终返回 5 - 2 = 3，而正确答案是 4。
  • 错误写法：阈值写成 cnt >= 1 → 用例 [1,0,1,1,0]，第一次遇到 0 就触发收缩，窗口内永远不允许有 0，退化成「最长连续 1」，返回 2。
  • 错误写法：cnt -= nums[l] ^ 1 之后忘记 l++ → 用例 [1,0,1,1,0]，左端点永远不动，cnt 会被反复减去同一个位置的值，最终返回 5 - 0 = 5，超过数组中任何合法段长度。
  • 错误写法：先 l++ 再用 nums[l] 计算，即写成 cnt -= nums[++l] ^ 1 → 用例 [1,0,1,1,0]，移出窗口的应该是 nums[0]，却减了 nums[1] 的贡献，cnt 从 2 变成 1，后续窗口计数与实际内容不符，[0,1,1,0,1] 这类输入会返回 5。
  • 错误写法：cnt += x ^ 1 写成 cnt += x → 用例 [1,0,1,1,0]，统计的变成了 1 的个数，读到下标 1 时 cnt 已是 1、下标 2 时变 2 触发收缩，返回值毫无意义（本例返回 2）。
  • 错误写法：把答案写成扫描过程中 Math.max(ans, i - l + 1) 却仍用 if 而非 while 收缩 → 用例 [1,0,1,1,0]，窗口 [1,4] 非法时长度 4 也被计入 max，虽然本例恰好等于正确答案，但换成 [0,0,0,0] 时窗口 [0,3] 长度 4 被记为答案，而正确答案是 1。
  • 错误写法：认为全 1 数组「没有 0 可翻」而特判返回 0 → 用例 [1,1,1]，cnt 始终为 0 从不收缩，正确返回 3，特判后返回 0。
  • 错误写法：认为全 0 数组无解返回 0 → 用例 [0,0,0]，翻掉一个 0 得到长度 1，期望 1；扫描中 l 会推进到 2，返回 3 - 2 = 1 本是对的，加了特判反而错。
  • 错误写法：先统计 0 的位置再枚举「翻掉第 j 个 0，答案为它前后两段 1 的长度和加一」，但忘记处理「数组中没有 0」和「只有一个 0」 → 用例 [1,1] 没有 0 时循环体一次都不执行，答案变量保持初值 0，期望 2。
  • 错误写法：把题意理解成「恰好翻一个 0」 → 用例 [1,1,1]，会去找一个不存在的 0 并返回 0 或抛异常，期望 3。

相似题目

题目 难度 考察点
424. 替换后的最长重复字符 中等 窗口内的「非法元素数」要减去出现次数最多的字符，需要额外维护频次表
485. 最大连续 1 的个数 简单 不允许翻转，一次计数即可，是本题 k = 0 的退化情形
1004. 最大连续1的个数 III 中等 把可翻转次数推广到 k，本题的阈值 1 直接换成 k 即可
1493. 删掉一个元素以后全为 1 的最长子数组 中等 必须删掉一个元素，答案要在窗口长度上再减 1，且全 1 时需特殊处理
面试题 05.03. 翻转数位 简单 输入是 32 位整数而非数组，需要边取位边滑窗，注意负数的符号位