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

约 5 分钟
文章信息 13 个分类 4 个标签
分类
LeetCode CodeTop 中等 已解决 已掌握 20-50 LeetCode 75 字节 华为 微软 拼多多 快手 B站
标签
数组 二分查找 滑动窗口 前缀和

题目描述

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

image-20260928202638791

题意分析

给定只包含零和一的数组，最多可以把 k 个零改成一，求最终能够获得的最长连续一的长度。可以少用翻转次数，不要求恰好使用 k 次，也不能通过删除元素把不相邻的位置连接起来。

对任意一段连续区间，要把它全部变成一，恰好需要翻转其中的所有零。因此问题等价于：寻找包含至多 k 个零的最长连续子数组。只需要统计零，不必真的修改数组。

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

核心思路

[!blue]

用闭区间 [left, right] 表示当前窗口，zeroCount 表示其中零的数量。右端每次向右加入一个元素，如果它是零，就把计数加一。只要 zeroCount <= k，这段区间就能在预算内全部变成一。

若零超过预算，就从左端依次移出元素，直到重新合法。移出一只缩短窗口，移出零才会减少所需翻转次数，因此收缩可能需要跨过多个一，不能保证只移动一次就够。

为什么不需要让左端回退？一个左端位置一旦因为零太多而被排除，右端继续扩大时，包含这个旧左端的区间只会拥有更多或相同数量的零，不可能重新变合法。反过来，收缩只在超额时进行，恢复合法后立刻停止，留下的是当前右端对应的最长合法窗口。

每个右端都检查一次这样得到的最大可用长度，就覆盖了全局最优答案的结束位置。必须先恢复合法，再用 right - left + 1 更新答案，才能保证记录的长度确实能由至多 k 次翻转得到。

k = 0 时，遇到零会收缩到它之后，窗口可以暂时为空，长度为零；全数组的零不超过预算时，左端始终不动，最终长度就是整个数组长度。这些边界都不需要额外分支。

解题步骤

  1. 初始化 left = 0、zeroCount = 0、ans = 0。
  2. 枚举右端 right，把新加入的零计入 zeroCount。
  3. 当 zeroCount > k 时，检查将要移出的 nums[left]；若为零，计数减一，然后推进左端。
  4. 窗口合法后，用 right - left + 1 更新最大长度。
  5. 处理完所有右端后返回答案。

代码实现

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)$。右端完整扫描数组一次，左端也只向右移动，最多经过每个位置一次；内层收缩的总次数为线性数量。
  • 空间复杂度：$O(1)$，只维护两个边界、零计数和答案，不修改或复制输入数组。

关键点总结

[!green]

  • 区间内的零数就是变成全一所需的翻转次数，把操作问题变成窗口约束。
  • 已排除的左端不会随着右端扩展重新变合法，所以两个指针都可以单向前进。
  • 零数等于预算时窗口仍合法，只在超过预算时收缩，恢复后才更新答案。

易错点总结

[!yellow]

  • 移出一时也减少 zeroCount，会低估窗口的真实翻转成本；只有移出零才减一。
  • 收缩条件写成 zeroCount >= k，会把恰好用完预算的合法区间也删除。
  • 只用一次条件判断移动左端，可能尚未移出任何零，窗口仍非法；当前写法要持续收缩到合法。
  • 在收缩前更新答案，可能把超过预算的区间长度记录为可行结果。
  • 窗口包含两端，长度为 right - left + 1；每轮重置左端或重新统计整段会破坏线性复杂度。

相似题目

题目 难度 关联与区别
487. 最大连续1的个数 II 中等 把最多翻一个0推广为最多k个0，窗口零计数预算相同。
1493. 删掉一个元素以后全为 1 的最长子数组 中等 原题必须删除一个位置，本题允许翻转至多k位，不能把全1数组的边界混用。
424. 替换后的最长重复字符 中等 维护窗口内可消耗的修改预算；本题预算为窗口内零的个数，该题预算为窗口长度减最大字符频次。
1208. 尽可能使字符串相等 中等 维护窗口内可消耗的修改预算；本题预算为窗口内零的个数，该题预算为对应字符差值之和。
2024. 考试的最大困扰度 中等 维护窗口内可消耗的修改预算；本题预算为窗口内零的个数，该题分别计算统一为两种答案时的窗口。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/75262525
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！