LeetCode 1004. 最大连续1的个数 III

约 5 分钟
文章信息 13 个分类 6 个标签
分类
LeetCode CodeTop 中等 已解决 已掌握 20-50 字节跳动 微软 快手 华为 拼多多 哔哩哔哩 LeetCode 75
标签
数组 二分查找 滑动窗口 前缀和 滑动窗口经典题 最大连续 1 问题
目录

题目描述

✅ 1004. 最大连续 1 的个数 III

image-20230307210905964

题意分析

给定一个只含 0 和 1 的数组，最多可以把 k 个 0 改成 1，问改完之后最长的一段连续 1 有多长。

「最多 k 个」意味着不必用满，而且改哪几个 0 完全自由。真正被问的是一段连续区间：只要某段区间里 0 的个数不超过 k，就能把它们全部翻成 1，这段区间整体变成连续的 1，长度就是这段区间的长度。所以答案等价于「最长的、内部 0 的个数不超过 k 的连续子数组长度」，翻转这个动作本身根本不用真的执行。

约束里数组长度可达 $10^5$，说明必须是线性或接近线性的做法，枚举所有区间的 $O(n^2)$ 会超时；k 的取值范围可以从 0 一直到数组长度，两端都要能正确处理。

边界上要留意：k = 0 时退化成「最长连续 1 的个数」；k 大于等于数组中 0 的总数时，整个数组都可以翻成 1，答案是数组长度；数组可能全是 0，此时答案是 k 与数组长度中的较小者。

解法：滑动窗口统计零的数量

核心思路

把区间内的 0 全部翻转后能得到连续 1，因此问题等价于：寻找包含不超过 k 个 0 的最长连续子数组。枚举所有区间需要 $O(n^2)$，而这个约束具有单调性：右端加入元素后若超标，只需不断右移左端，之后左端没有必要回退，所以适合滑动窗口。

维护窗口 [left, right] 以及其中 0 的数量 zeroCount。每轮先加入 nums[right]；若 zeroCount > k，就从左侧移出元素，直到窗口重新合法。

循环不变量：更新答案前，窗口内至多有 k 个 0，并且 left 没有多移动——若把它向左扩一格，窗口就会包含超过 k 个 0。因此 [left, right] 是以 right 结尾的最长合法区间。任何最优答案都有一个右端点，扫描到该位置时不会漏掉它，所以取所有窗口长度的最大值即可。

解题步骤

  1. 初始化 left = 0、zeroCount = 0、ans = 0。
  2. 枚举右端点 right；若新元素是 0，令 zeroCount++。
  3. 当 zeroCount > k 时移动 left。移出的元素若为 0，同时令 zeroCount--。
  4. 窗口恢复合法后，用 right - left + 1 更新最大长度。
  5. 扫描结束后返回 ans。

例如 [1, 1, 0, 0, 1, 1, 1]、k = 1：第二个 0 进入后窗口超标，左端移动到第一个 0 之后；随后窗口可扩展为 [0, 1, 1, 1]，最长长度为 4。k = 0 时同一逻辑自然退化为最长连续 1。

代码实现

class Solution {
    public int longestOnes(int[] nums, int k) {
        int left = 0;
        int zeroCount = 0;
        int ans = 0;

        for (int right = 0; right < nums.length; right++) {
            if (nums[right] == 0) {
                zeroCount++;
            }
            while (zeroCount > k) {
                if (nums[left] == 0) {
                    zeroCount--;
                }
                left++;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

func longestOnes(nums []int, k int) int {
    left := 0
    zeroCount := 0
    ans := 0

    for right := 0; right < len(nums); right++ {
        if nums[right] == 0 {
            zeroCount++
        }
        for zeroCount > k {
            if nums[left] == 0 {
                zeroCount--
            }
            left++
        }
        if right-left+1 > ans {
            ans = right - left + 1
        }
    }
    return ans
}

复杂度分析

  • 时间复杂度：$O(n)$。left、right 都只向右移动，各自最多遍历数组一次。
  • 空间复杂度：$O(1)$。只维护窗口边界、0 的数量和答案。

关键点总结

  • 不必真的翻转元素，只需约束窗口内 0 的数量不超过 k。
  • 滑动窗口成立的依据是：缩小区间只会减少 0，不会让合法窗口变得非法。
  • 固定流程是「右侧加入 → 超标时左侧移出 → 窗口合法后更新答案」。
  • 内层循环总成本由左指针的单向移动摊还，因此不是 $O(n^2)$。

易错点总结

  • 移出 1 时也减少 zeroCount：会让计数偏小；只有移出 0 才能减一。
  • 收缩条件写成 zeroCount >= k：会把恰好使用 k 次翻转的合法窗口也删掉，应使用 > k。
  • 收缩前更新答案：如 [0, 0]、k = 1 会把非法长度 2 计入答案。
  • 窗口长度写成 right - left：闭区间长度应为 right - left + 1。
  • 每轮重置 left 或重新统计窗口：会失去指针单调性，复杂度退化为 $O(n^2)$。

相似题目

题目 难度 考察点
485. 最大连续 1 的个数 简单 本题 k = 0 的特例，一次遍历累计并在遇 0 时清零即可
487. 最大连续1的个数 II 中等 本题 k = 1 的特例，也可用「记住上一个 0 的位置」的双变量写法
424. 替换后的最长重复字符 中等 字符集扩大到 26 个，合法条件变为「窗口长度减去出现次数最多的字符数不超过 k」
1493. 删掉一个元素以后全为 1 的最长子数组 中等 必须删且只删一个元素，答案要减一，全 1 输入是关键边界
面试题 05.03. 翻转数位 简单 载体从数组换成 32 位整数的二进制位，需要边取位边滑窗