最大连续 1 的个数 III 图解题解

这道题到底在问什么

nums

[1,1,0,1,1,1,0,0,1,1,1]

k

2

输出

8

最优解：一步一步想明白

1. 3「翻 k 个 0」这个动作其实不用真去翻。只要一段连续区间里 0 不超过 k 个,它就能全变成 1。问题就化简成:0 不超标的最长区间有多长。
2. 4对每个起点都从头往右扫一遍,能做对,但起点有 n 个、每次又要扫 n 个,白白重复了大量计算,是 O(n²)。
3. 5因为答案区间一定是一段连续的。维护一个窗口 [l, r],右端 r 不停往右伸;只有当窗口里 0 太多(超过 k)时,才把左端 l 往右收。l 永远不回头。
4. 6想象一个橡皮筋框,右边一直往外撑(r++);一旦框里 0 超标,左边就跟着往里收(l++),直到框里 0 又 ≤ k。l 和 r 都只朝一个方向走,合起来只走 n 步,O(n)。
5. 7k = 2, 窗口为空数组摆好,k=2 表示窗口里最多容忍 2 个 0。l 是窗口左端、r 是右端。现在窗口还空着,让 r 一格一格往右伸。
6. 80计数=0 ≤ 2 ✓ · 窗口[0,0] 长1r 伸到下标 0,值是 1(不占翻牌名额)。窗口里 0 个数还是 0,没超标。当前长 1,最大长度记成 1。
7. 90计数=0 ≤ 2 ✓ · 窗口[0,1] 长2r 伸到下标 1,还是 1。窗口 [0,1] 里 0 个数仍是 0,合法。最大长度更新到 2。
8. 100计数=1 ≤ 2 ✓ · 窗口[0,2] 长3r 伸到下标 2,是个 0,占掉一个翻牌名额,0计数变成 1。1 ≤ 2 还在预算内,窗口不收,长度到 3。
9. 110计数=1 ≤ 2 ✓ · 窗口[0,3] 长4r 到下标 3 是 1,不占名额,0计数还是 1,合法。窗口越伸越长,最大长度到 4。
10. 120计数=1 ≤ 2 ✓ · 窗口[0,4] 长5r 到下标 4,继续白嫖伸长。窗口 [0,4] 里仍只有 1 个 0,合法,最大长度到 5。
11. 130计数=1 ≤ 2 ✓ · 窗口[0,5] 长6r 到下标 5,又是 1。窗口 [0,5] 长 6,里面只有 1 个 0,合法,最大长度到 6。
12. 140计数=2 ≤ 2 ✓ · 窗口[0,6] 长7r 到下标 6,又是 0,0计数升到 2,正好把 k=2 的名额用满。≤ k 才合法,等于也算合法,窗口不收,最大长度到 7。
13. 150计数=3 > 2 ✗ · 必须收左端r 到下标 7,又一个 0,0计数飙到 3,超过 k=2 了!窗口非法。该收左端 l——一直收到窗口里 0 重新 ≤ 2 为止。
14. 160计数仍=3 · 继续收l 往右收一格,移出下标 0 的 1。移出的是 1,不影响 0 的个数,0计数还是 3,仍超标,继续收。
15. 170计数仍=3 · 继续收l 再收一格,移出下标 1 的 1,还是不减 0计数。0 仍有 3 个,继续往右收 l。
16. 18移出 1 个 0 · 0计数=2 ≤ 2 ✓ · 合法了l 收到下标 2,移出的是 0!0计数从 3 降回 2,窗口 [3,7] 重新合法,停止收缩。注意:整个收缩里最大长度 7 没被刷掉——当前窗口长 5,没它长。
17. 190计数=2 ≤ 2 ✓ · 窗口[3,8] 长6r 伸到下标 8,是 1,合法。窗口 [3,8] 长 6,还没超过历史最大 7,先不更新。
18. 200计数=2 ≤ 2 ✓ · 窗口[3,9] 长7r 到下标 9,还是 1。窗口 [3,9] 长 7,追平历史最大 7。再伸一格会怎样?
19. 210计数=2 ≤ 2 ✓ · 窗口[3,10] 长8r 到最后一格下标 10,是 1,合法。窗口 [3,10] 长 8,超过了之前的 7,最大长度刷新成 8!数组走完了。
20. 22历史最大窗口长度 = 8整个过程出现过的最长合法窗口是绿色这段 [3,10],长度 8。把里头两个 0 翻成 1 后,能凑出 8 个连续的 1。l 和 r 全程都只往右走,一趟扫完。
21. 23l 一共只往右走 n 步、r 也只往右走 n 步,加起来 2n 次操作,化简就是 O(n),重复扫描被彻底消掉。
22. 24nums=[1,1,0,0,1,1,1,0,0,1,1] k=2换一组数据再走关键几步,专门体会:当 0 接连出现,左端会分两次收缩。窗口先空着,r 准备右扩。
23. 250计数=2 ≤ 2 ✓ · 当前最大 7快进:r 一路伸到下标 6,中间下标 2、3 两个 0 把名额用满但没超标。窗口 [0,6] 长 7,最大记 7。
24. 260计数=3 > 2 ✗ · 收左端r 到下标 7 又是 0,0计数=3 超标。开始收左端:得一直收到把一个 0 移出窗口为止。
25. 270计数=2 ≤ 2 ✓ · 合法l 连收三格,前两格是 1(不减计数),收到下标 2 的 0 才让 0计数降回 2,窗口 [3,7] 合法,停。
26. 280计数=3 > 2 ✗ · 再收一次紧接着 r 到下标 8 又是 0,0计数再次冲到 3,又超标!这就是「收缩会发生第二次」——所以收缩必须能反复触发。
27. 290计数=2 ≤ 2 ✓ · 又合法这次只收一格:移出下标 3 的 0,0计数降回 2 就合法了。当前窗口长 5,没超过历史最大 7。两次收缩都靠同一段 while 完成——这正是收缩要用 while 的原因。
28. 32凡是「求满足某条件的最长/最短连续区间」,且条件满足单调性(窗口越大越容易违规)的题,第一反应就该想到滑动窗口。
29. 33本题求最长,所以让窗口尽量大,只在不得不收时才收。若题目求最短合法区间,模板改成:窗口一合法就拼命收左端、边收边记最短。看清「最长 / 最短」,模板方向就定了。
30. 35移出了 0 却没减 → 计数虚高假设 k=1,窗口收缩把下标 0 的 0 移出去了,但代码忘了 zeros−1。于是这个已离开窗口的 0 还被算在账上,0计数虚高,后面会误判超标、把好窗口白白收掉。移出 0 必须同步减计数。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def longestOnes(self, nums, k):
        l = 0            # 窗口左端
        zeros = 0        # 窗口内 0 的个数
        ans = 0
        for r in range(len(nums)):   # r 右扩
            if nums[r] == 0:
                zeros += 1            # 新进来一个 0
            while zeros > k:          # 超标就收左端
                if nums[l] == 0:
                    zeros -= 1
                l += 1
            ans = max(ans, r - l + 1)  # 更新最大窗口
        return ans

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int l = 0, zeros = 0, ans = 0;   // 左端/0计数/答案
        for (int r = 0; r < (int)nums.size(); r++) {
            if (nums[r] == 0) zeros++;   // r 进来个 0
            while (zeros > k) {          // 超标收左端
                if (nums[l] == 0) zeros--;
                l++;
            }
            ans = max(ans, r - l + 1);   // 更新最大窗口
        }
        return ans;
    }
};

class Solution {
    public int longestOnes(int[] nums, int k) {
        int l = 0, zeros = 0, ans = 0;   // 左端/0计数/答案
        for (int r = 0; r < nums.length; r++) {
            if (nums[r] == 0) zeros++;   // r 进来个 0
            while (zeros > k) {          // 超标收左端
                if (nums[l] == 0) zeros--;
                l++;
            }
            ans = Math.max(ans, r - l + 1); // 更新最大窗口
        }
        return ans;
    }
}

复杂度

面试官可能追问