1004. 最大连续1的个数 III：滑动窗口（结合贪心策略？）.md

题目简述：

给定一个二进制数组 nums 和一个整数 k，假设最多可以翻转 k 个 0 ，则返回执行操作后 数组中连续 1 的最大个数 。

题目链接：1004. 最大连续1的个数 III

思路

滑动窗口问题。

但我总觉得我的实现里有一点贪心策略的思想。因为算法实际上在 “寻找尽可能更大的窗口宽度”。即，right 尽可能扩张，为保证 right 的扩张合法，left 需要借助额外的逻辑进行更新以确保 right 能够继续探索。

虽然设计出了能够 AC 且高效的算法代码，但我也说不准为什么这样得到的解就是全局最优解。以下是 GPT-5 的回答：

不变量

在任意时刻（处理到下标 right 后），令窗口为 [left, right]，并记其中 0 的个数为 Z。算法始终保持：

1. 合法性：Z ≤ k（窗口内最多 k 个 0，可全翻）。
2. 最小左端：在固定的 right 下，当前 left 是所有合法窗口中最小的起点——即再往左一步就会使 Z > k。

你代码里虽然用的是“额度 k 递减 + 碰到 0 且无额度时跳过第一个 0”，但等价于维护了上面两个条件（我们之前讨论过的等式 Z = K - k 让 1) 成立，而“跳到第一个 0 的后面”让 2) 成立）。

关键引理（最小收缩的必要性与充分性）

当遇到一个 0 且当前已用满额度时（Z == k），任何以该 right 结尾的合法窗口的左端都必须不早于“窗口内第一个 0 的后一个位置”。

• 必要性：如果左端还在那个 0 的左边，则窗口里至少有 k+1 个 0（超标）。
• 充分性：把左端移到该 0 的后面，窗口中恰少一个 0，变回合法；且这是最小的合法起点。

因此，你的“收缩到第一个 0 后”就是最小代价恢复合法性的贪心动作。

以右端为轴的最优性（核心一步）

对任意 right，设算法最终的左端是 L(right)。

• 由于上面 2)，凡是以 right 结尾的合法窗口，其起点 l 必须满足 l ≥ L(right)；
• 因而在这些窗口里，长度最大的就是当前窗口 [L(right), right] 本身。 所以：算法在每个 right 上都得到“以 right 为结尾”的最长合法区间。

全局最优

答案是所有 right 的这些最长值的最大者。算法逐个 right 更新最大值，因此全局最优。

贪心为何成立（一句话版）

合法性对左端是单调的（左端右移只会减少 0），而目标（区间长度）对左端是单调不增。 所以当超标时，把左端贪心地移到“刚好合法”的最小位置，既恢复了可行性，又不丢失任何以当前 right 结尾的更长候选。

哦，GPT-5 的回答看到一半，我就明白了：因为能够保证算法中每个以 right 为右端点的窗口，恰恰就是以 right 为右端点的窗口中最长的那一个——我们尽可能翻转 0 以使得 left 最小，这样窗口跨度就是最大的。因此，当 right 遍历了一次数组，我们就探索了数组中每个元素作为窗口右端点时的窗口最大值，那么这些每个条件下的最长窗口合起来取最值就是全局最大的窗口。

代码

class Solution {
    public int longestOnes(int[] nums, int k) {
        int n = nums.length;
        int maxWidth = 0;
        int left = 0;

        for (int right = 0; right < n; right++) {
            if (nums[right] == 1) {
                maxWidth = Math.max(maxWidth, right - left + 1);
            } else if (nums[right] == 0 && k > 0) {
                maxWidth = Math.max(maxWidth, right - left + 1);
                k--;
            } else if (nums[left] == 0) {
                left++;
            } else {
                do {
                    left++;
                } while (nums[left] != 0);

                left++;
            }
        }

        return maxWidth;
    }
}