最大连续 1 的个数 III

「翻 k 个 0」这个动作其实不用真去翻。只要一段连续区间里 0 不超过 k 个,它就能全变成 1。问题就化简成:0 不超标的最长区间有多长。

对每个起点都从头往右扫一遍,能做对,但起点有 n 个、每次又要扫 n 个,白白重复了大量计算,是 O(n²)。

因为答案区间一定是一段连续的。维护一个窗口 [l, r],右端 r 不停往右伸;只有当窗口里 0 太多(超过 k)时,才把左端 l 往右收。l 永远不回头。

想象一个橡皮筋框,右边一直往外撑(r++);一旦框里 0 超标,左边就跟着往里收(l++),直到框里 0 又 ≤ k。l 和 r 都只朝一个方向走,合起来只走 n 步,O(n)。

准备 · l=r=0, 0计数=0：数组摆好,k=2 表示窗口里最多容忍 2 个 0。l 是窗口左端、r 是右端。现在窗口还空着,让 r 一格一格往右伸。

r=0 看 1：r 伸到下标 0,值是 1(不占翻牌名额)。窗口里 0 个数还是 0,没超标。当前长 1,最大长度记成 1。

r=1 看 1：r 伸到下标 1,还是 1。窗口 [0,1] 里 0 个数仍是 0,合法。最大长度更新到 2。

r=2 看 0：r 伸到下标 2,是个 0,占掉一个翻牌名额,0计数变成 1。1 ≤ 2 还在预算内,窗口不收,长度到 3。

r=3 看 1：r 到下标 3 是 1,不占名额,0计数还是 1,合法。窗口越伸越长,最大长度到 4。

r=4 看 1：r 到下标 4,继续白嫖伸长。窗口 [0,4] 里仍只有 1 个 0,合法,最大长度到 5。

r=5 看 1：r 到下标 5,又是 1。窗口 [0,5] 长 6,里面只有 1 个 0,合法,最大长度到 6。

r=6 看 0：r 到下标 6,又是 0,0计数升到 2,正好把 k=2 的名额用满。≤ k 才合法,等于也算合法,窗口不收,最大长度到 7。

r=7 看 0 · 超标!：r 到下标 7,又一个 0,0计数飙到 3,超过 k=2 了!窗口非法。该收左端 l——一直收到窗口里 0 重新 ≤ 2 为止。

收左端 · l=0 是 1, 移出：l 往右收一格,移出下标 0 的 1。移出的是 1,不影响 0 的个数,0计数还是 3,仍超标,继续收。

收左端 · l=1 是 1, 移出：l 再收一格,移出下标 1 的 1,还是不减 0计数。0 仍有 3 个,继续往右收 l。

收左端 · l=2 是 0, 移出!：l 收到下标 2,移出的是 0!0计数从 3 降回 2,窗口 [3,7] 重新合法,停止收缩。注意:整个收缩里最大长度 7 没被刷掉——当前窗口长 5,没它长。

r=8 看 1：r 伸到下标 8,是 1,合法。窗口 [3,8] 长 6,还没超过历史最大 7,先不更新。

r=9 看 1：r 到下标 9,还是 1。窗口 [3,9] 长 7,追平历史最大 7。再伸一格会怎样?

r=10 看 1 · 刷新纪录!：r 到最后一格下标 10,是 1,合法。窗口 [3,10] 长 8,超过了之前的 7,最大长度刷新成 8!数组走完了。

扫描结束 · 答案：整个过程出现过的最长合法窗口是绿色这段 [3,10],长度 8。把里头两个 0 翻成 1 后,能凑出 8 个连续的 1。l 和 r 全程都只往右走,一趟扫完。

l 一共只往右走 n 步、r 也只往右走 n 步,加起来 2n 次操作,化简就是 O(n),重复扫描被彻底消掉。

再演一例 · 看「两次收缩」：换一组数据再走关键几步,专门体会:当 0 接连出现,左端会分两次收缩。窗口先空着,r 准备右扩。

r 直冲到 6 · 窗口[0,6] 长7：快进:r 一路伸到下标 6,中间下标 2、3 两个 0 把名额用满但没超标。窗口 [0,6] 长 7,最大记 7。

r=7 看 0 · 第 1 次超标：r 到下标 7 又是 0,0计数=3 超标。开始收左端:得一直收到把一个 0 移出窗口为止。

收到 l=3 · 移出下标2 的 0：l 连收三格,前两格是 1(不减计数),收到下标 2 的 0 才让 0计数降回 2,窗口 [3,7] 合法,停。

r=8 看 0 · 第 2 次超标：紧接着 r 到下标 8 又是 0,0计数再次冲到 3,又超标!这就是「收缩会发生第二次」——所以收缩必须能反复触发。

收到 l=4 · 移出下标3 的 0：这次只收一格:移出下标 3 的 0,0计数降回 2 就合法了。当前窗口长 5,没超过历史最大 7。两次收缩都靠同一段 while 完成——这正是收缩要用 while 的原因。

凡是「求满足某条件的最长/最短连续区间」,且条件满足单调性(窗口越大越容易违规)的题,第一反应就该想到滑动窗口。

本题求最长,所以让窗口尽量大,只在不得不收时才收。若题目求最短合法区间,模板改成:窗口一合法就拼命收左端、边收边记最短。看清「最长 / 最短」,模板方向就定了。

雷区实演 · l 移出 0 不减计数：假设 k=1,窗口收缩把下标 0 的 0 移出去了,但代码忘了 zeros−1。于是这个已离开窗口的 0 还被算在账上,0计数虚高,后面会误判超标、把好窗口白白收掉。移出 0 必须同步减计数。

边界三连：先想最严(k=0)、最宽(k 够大)、最极端(全 0 且 k=0)三种,代码就稳了。

面试追问：把「O(n)」「为什么是滑窗」「最长 vs 最短」讲透,是这题的面试得分点。