你好，同学。今天我们来挑战一道在 NOI 普及组/提高组初阶非常高频的变长滑动窗口题目。

这道题考察的是将“动态变化”转化为“区间特征”的能力。在 LeetCode 上它叫“最大连续 1 的个数 III”，在竞赛中，我们更倾向于把它看作是双指针维护单调性的典型应用。

一、 预备知识点

1. 滑动窗口（双指针）：掌握 left 和 right 指针的协同移动。
2. 问题等价转换：理解“最多翻转 $k$ 个 0”等价于“寻找一个包含最多 $k$ 个 0 的最长子数组”。
3. 区间计数：在 $O(1)$ 时间内动态更新当前窗口内 0 的个数。

二、 题目描述 (NOI 竞赛风格)

题目名称：最大连续 1 的个数 III (Max Consecutive Ones III)

【问题描述】 给定一个由若干 0 和 1 组成的数组 $A$，以及一个整数 $K$。 我们可以将最多 $K$ 个值从 0 翻转为 1。 请输出在进行上述翻转后，数组中连续 1 的最大长度。

【输入格式】 第一行包含两个整数 $n$ 和 $K$，分别表示数组长度和允许翻转的最大次数。 第二行包含 $n$ 个以空格分隔的整数（只能是 0 或 1），表示数组 $A$。

【输出格式】 输出一个整数，表示连续 1 的最大长度。

【样例 1 输入】

11 2
1 1 1 0 0 0 1 1 1 1 0

【样例 1 输出】

6

(解释：翻转下标为 5, 10 的 0，或者翻转下标为 3, 4 的 0。最长连续 1 长度为 6。)

【数据规模与约定】

• $1 \le n \le 10^5$
• $0 \le K \le n$
• $A[i]$ 为 $0$ 或 $1$

三、 启发式引导：草稿纸上的推理过程

来，拿出草稿纸，我们换个视角看这道题。

第一步：核心逻辑转换

思考： 如果我们要找翻转后的最长连续 1，那这段区间在翻转前长什么样？

• 观察： 它原本是一段包含 1 和 0 的区间，只要这段区间里 0 的个数 $\le K$，我们就能把它们全部变白（变 1）。
• 结论： 题目转化为——求一个最长的子数组，使得其中 0 的个数不超过 $K$。

第二步：寻找单调性

思考： 如果区间 $[L, R]$ 内的 0 已经超过了 $K$ 个，那么区间 $[L, R+1]$ 呢？

• 观察： 0 的个数只会增加，不会减少。
• 操作： 此时我们必须右移左边界 $L$，来剔除掉一些 0。

第三步：模拟滑动窗口

在草稿纸上画出双指针的律动：

1. right 不断向右跑，每碰到一个 0，计数器 cnt0 就加 1。
2. 如果 cnt0 > K，说明现在的窗口“透支”了翻转次数。
3. left 开始向右缩，如果缩掉的是 0，cnt0 就减 1，直到 cnt0 <= K 为止。
4. 过程中，right - left + 1 的最大值就是我们要的答案。

第四步：复杂度分析与思考

• 时间复杂度：每个元素进入窗口一次，离开窗口一次。虽然有内外循环，但 $O(2N)$ 本质上是 $O(N)$。对于 $10^5$ 的数据，1 秒绰绰有余。
• 空间复杂度：只需存储原数组，$O(N)$。

四、 算法逻辑流程图

在 NOI 竞赛中，逻辑的严密性高于一切。请参考以下流程图构思你的代码：

graph TD
    A[开始] --> B[读取 n 和 K]
    B --> C[初始化: left=0, ans=0, zero_cnt=0]
    C --> D[for right 从 0 到 n-1]
    D --> E{nums_right == 0?}
    E -- 是 --> F[zero_cnt++]
    E -- 否 --> G{zero_cnt > K?}
    F --> G
    G -- 是 --> H{nums_left == 0?}
    H -- 是 --> I[zero_cnt--]
    H -- 否 --> J[left++]
    I --> J
    J --> G
    G -- 否 --> K[ans = max_ans, right-left+1]
    K --> L{right == n-1?}
    L -- 否 --> D
    L -- 是 --> M[输出 ans]
    M --> N[结束]

五、 总结：读题关键词与优化建议

读题关键词：

1. “最大连续”：通常暗示滑动窗口或前缀和+二分。
2. “翻转/修改最多 $K$ 次”：这是变长滑动窗口的典型约束条件。
3. “0 和 1 数组”：提示你可以利用简单的累加或计数来监控区间特征。

时间复杂度优化建议：

• 常规优化：$O(N)$ 已经是此题最优。
• 常数级优化：在收缩 left 的 while 循环中，可以直接判断 $K$ 是否为 0。如果 $K=0$，逻辑会有微小差别。
• 不收缩窗口技巧（进阶）：在某些场景下，我们可以维护一个“只增大不缩小”的窗口。即当 cnt0 > K 时，left 只随 right 同步右移一步，而不是收缩到满足条件。这样窗口的长度始终保持为目前发现的最大值。

教练点评： 这道题的精髓在于**“把约束条件转化为窗口的属性”**。在草稿纸上，如果你能准确写出 zero_cnt <= K 这个判定式，这道题你就已经赢了一半。剩下的就是处理好 left 移动时的边界问题，不要多减也不要少减。加油！