04 最长扩张型可变窗口：替换操作与连续性约束

最长扩张型可变窗口：替换操作与连续性约束

摘要

本篇讲解一类特殊但高频的可变窗口题型：允许在窗口内进行有限次”替换操作”以满足连续性约束。代表题目是 LeetCode 424（最长重复字符替换）和 LeetCode 1004（最大连续 1 的个数 III）。这类题目有一个著名的反直觉优化——当窗口不合法时，不收缩窗口，而是维持窗口大小继续扩张。理解这个”不缩反扩”的思路，是本篇的核心目标。此外，本篇还涵盖 LeetCode 1493（删掉一个元素以后全为 1 的最长子数组），演示替换思想从”字符串”到”数组”的迁移。

---

第 1 章 替换操作的抽象：将”修改”纳入窗口合法性

1.1 一类新的合法性定义

前几篇的窗口合法性是”窗口内的元素满足某个不变条件”——如”无重复字符”、“包含目标字符集”。

这类可变窗口的合法性定义不同：窗口内的元素通过有限次操作（替换/删除），可以变得满足某个连续性条件。

具体来说：

• 424：至多可以替换 $k$ 个字符，使得窗口内的字符全部变成同一个字母（最长单字母字符串）
• 1004：至多可以翻转 $k$ 个 0，使得窗口内全为 1（最长连续 1 序列）
• 1493：删掉恰好 1 个元素，使得剩余元素全为 1（最长连续 1 子数组）

这三道题的本质是一样的：窗口内有一些”坏元素”（需要替换/删除的元素），合法条件是”坏元素个数 ≤ k”。

1.2 “坏元素个数”的增量维护

定义”坏元素”后，窗口的合法性变得简单：

• 1004 / 1493：“坏元素”就是 0，直接计数 zeros = 窗口内 0 的个数，合法条件是 zeros <= k
• 424：稍复杂。“坏元素”是窗口内不是”最多出现字符”的字符。设窗口大小为 len，最多出现字符的频率为 maxFreq，则坏元素个数是 len - maxFreq，合法条件是 len - maxFreq <= k

zeros 的增量维护很简单：进 0 时 zeros++，出 0 时 zeros--。

maxFreq 的增量维护是本题的精妙之处，将在第 2 章详细讨论。

---

第 2 章 LeetCode 1004：最大连续 1 的个数 III

2.1 题目

LeetCode 1004 - Max Consecutive Ones III（中等）

给你一个二进制数组 nums 和一个整数 k，如果可以将 $k$ 个 0 翻转成 1，返回数组中连续 1 的最大个数。

输入：nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
输出：6
解释：翻转 index 5、10 的 0，得到 [1,1,1,0,0,1,1,1,1,1,1]，最长连续 1 序列是 6

输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1,0], k = 3
输出：10

2.2 转化视角：窗口内 0 的个数 ≤ k

与其说”翻转 k 个 0”，不如说”找最长的子数组，其中 0 的个数不超过 k”。这两种表述完全等价——翻转窗口内的所有 0（代价是 k 次操作），可以让整个子数组变为连续 1。

这是一个标准的”最长合法窗口”问题：

• 窗口状态：zeros（窗口内 0 的个数）
• 合法条件：zeros <= k
• 目标：最大化窗口长度

public int longestOnes(int[] nums, int k) {
    int left = 0, zeros = 0, maxLen = 0;
 
    for (int right = 0; right < nums.length; right++) {
        // 进窗
        if (nums[right] == 0) zeros++;
 
        // 收缩：当 0 的个数超过 k 时，收缩左边界
        while (zeros > k) {
            if (nums[left] == 0) zeros--;
            left++;
        }
 
        // 更新答案（此时窗口合法）
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

时间复杂度：$O(n)$，每个元素进出各一次 空间复杂度：$O(1)$

这道题用上面的代码可以一次过，逻辑非常干净。但 LeetCode 424 要复杂得多。

2.3 LeetCode 1493：删掉一个元素以后全为 1 的最长子数组

LeetCode 1493（中等）是 1004 的变体：删掉恰好 1 个元素（而不是”至多 k 个 0 翻转为 1”），使得剩余子数组全为 1。

关键差异：是”恰好删 1 个”，不是”至多删 1 个”。如果原数组已经全为 1，删掉 1 个后长度减 1。

等价转化：找最长子数组使得其中恰好有 1 个 0（删掉这个 0，剩余全为 1）。但如果整个数组全为 1，那么随便删一个 1，结果是 n-1。

更简洁的做法：把”删一个元素”看成”至多有 1 个 0 的最长子数组”，但最终长度要减 1（因为删了一个元素）：

public int longestSubarray(int[] nums) {
    // 找至多包含 1 个 0 的最长子数组，长度减 1（因为必须删一个元素）
    int left = 0, zeros = 0, maxLen = 0;
 
    for (int right = 0; right < nums.length; right++) {
        if (nums[right] == 0) zeros++;
 
        while (zeros > 1) {
            if (nums[left] == 0) zeros--;
            left++;
        }
 
        maxLen = Math.max(maxLen, right - left + 1);
    }
 
    return maxLen - 1;  // 减 1：因为必须删掉一个元素
}

这道题把”删”操作巧妙地转化为”允许窗口内存在至多 1 个 0”，与 1004 几乎完全相同，只是最后答案减 1。

设计哲学：恰好 vs 至多

“恰好”和”至多”是算法题中经常需要转换的概念。“恰好 1 个 0”等价于”至多 1 个 0 的最长窗口，然后减去这 1 个 0 的长度贡献”。在第 09 篇”恰好 K 型窗口”中，这个转换会更系统地讨论。

---

第 3 章 LeetCode 424：最长重复字符替换

3.1 题目

LeetCode 424 - Longest Repeating Character Replacement（中等）

给你一个字符串 s 和一个整数 k，你可以对字符串中的任意字符进行替换，最多替换 k 次，返回替换后包含相同字母的最长子字符串的长度。

输入：s = "ABAB", k = 2
输出：4
解释：将两个 'A' 替换为 'B'（或反之），整个字符串变为 "BBBB" 或 "AAAA"

输入：s = "AABABBA", k = 1
输出：4
解释：将 index 4 的 'A' 替换为 'B'，得到 "AABBBBA"，最长连续相同字符子串是 "BBBB"，长度 4

3.2 合法性分析

窗口 $[left,right]$“合法”的含义：至多替换 $k$ 个字符，可以让窗口内所有字符变成同一个字母。

最优策略是：保留窗口内出现最多的那种字符，把其他字符都替换成它。这样替换次数最少。

因此，合法条件是： $\text{窗口大小}-\text{窗口内出现最多字符的频率}\le k$

即：$(right-left+1)-\text{maxFreq}\le k$

3.3 难点：maxFreq 的维护

进窗时，maxFreq 容易更新：maxFreq = Math.max(maxFreq, freq[inChar])。

出窗时，麻烦来了：出窗字符的频率减少后，maxFreq 应该怎么更新？如果出窗的字符恰好是最高频字符，它的频率降低，新的 maxFreq 可能变小。但找新的 maxFreq 需要扫描整个 freq 数组，$O(26)$ 的操作。

从均摊角度看，$O(26n)=O(n)$，理论上可行。但有一个更精妙的做法：不更新 maxFreq。

3.4 “不缩反扩”的反直觉优化

关键观察：我们只关心最大窗口大小，所以 maxFreq 只需要增加，不需要减少。

为什么？我们在寻找”合法窗口的最大长度”。假设历史上某个时刻，窗口大小为 $L$，其中最高频字符出现了 $f$ 次，合法条件 $L-f\le k$ 满足。

此后，即使某次操作导致出窗字符是最高频字符，$f$ 降低了——但只要新的窗口大小仍然是 $L$（我们不收缩窗口，只是”平移”），答案就不会变差。如果新右端点带来的字符让某个频率超过了旧 $f$，答案可能变好（窗口可以继续扩展）。

所以，正确的做法是：maxFreq 只在进窗时可能增加，出窗时保持不变。这样 maxFreq 是历史最高频率，可能比当前实际值大，但不影响正确性——因为：

• 如果 maxFreq 被高估了，合法条件 $(len-maxFreq\le k)$ 会变得”更难满足”（被高估的 maxFreq 让 $len-maxFreq$ 更小，似乎合法性更容易满足）
• 更准确地说：当 maxFreq 是历史最高时，窗口的大小 = maxFreq + k + 可能更多（左指针只有在窗口不合法时才前进）。这保证了最终答案不会遗漏。

public int characterReplacement(String s, int k) {
    int n = s.length();
    int[] freq = new int[26];
    int left = 0;
    int maxFreq = 0;
    int maxLen = 0;
 
    for (int right = 0; right < n; right++) {
        // 进窗
        int c = s.charAt(right) - 'A';
        freq[c]++;
        maxFreq = Math.max(maxFreq, freq[c]);  // 只更新，不回退
 
        // 检查合法性：窗口大小 - 最高频率 <= k
        int windowLen = right - left + 1;
        if (windowLen - maxFreq > k) {
            // 窗口不合法，左边出窗（注意：不是 while 循环，只移动一步）
            freq[s.charAt(left) - 'A']--;
            left++;
            // maxFreq 不更新，保持历史最高值
        }
 
        // 此时 right - left + 1 要么是合法窗口，要么与上一次合法窗口等大（平移）
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

注意：这里的收缩用的是 if 而不是 while！每次右指针前进一步，窗口大小最多增加 1；不合法时左指针也前进一步，窗口大小恢复原状（平移）。窗口大小要么增大 1（合法），要么不变（平移），永远不会减小。

3.5 为什么用 if 而不是 while

这是这道题最精妙的地方，值得深入分析。

用 while 的逻辑（正确但多余）：当窗口不合法时，不断收缩直到合法。但每次右指针只前进一步，窗口大小最多增加 1，不合法时只需收缩 1 步就能恢复到上一次的大小（不会更坏）。

用 if 的逻辑（等价且更高效）：当不合法时，窗口等大平移（左右各前进一步），维持窗口大小不变。当合法时，窗口扩大一步。由于我们求的是最大窗口，窗口大小从不减小——这正是我们想要的。

形象理解：把窗口想象成一段水平的尺子，在字符串上从左往右滑动。尺子只会变长（当发现更好的机会），不会变短（即使当前不合法，也只是原地平移，等待更好的机会）。

核心概念：为什么 maxFreq 不更新是正确的

设历史最高 maxFreq = $f$，此后出窗字符是最高频字符，窗口内最高频变成了 $f-1$。但窗口大小 = $f+k+1$（刚平移后的大小）。下一次右指针前进后，窗口大小 = $f+k+2$，最高频变成 $f$ 才能满足合法条件……这说明只有当某个字符频率再次达到 $f$ 时，窗口才会继续扩张。而 maxFreq 保持在 $f$，正确地反映了”需要至少 $f$ 的最高频才能让更大窗口合法”的条件。

3.6 完整追踪示例

以 s = "AABABBA", k = 1 为例追踪：

初始：left=0, maxFreq=0, freq=[]

right=0, c='A': freq={A:1}, maxFreq=1, len=1, 1-1=0<=1 合法, maxLen=1
right=1, c='A': freq={A:2}, maxFreq=2, len=2, 2-2=0<=1 合法, maxLen=2
right=2, c='B': freq={A:2,B:1}, maxFreq=2, len=3, 3-2=1<=1 合法, maxLen=3
right=3, c='A': freq={A:3,B:1}, maxFreq=3, len=4, 4-3=1<=1 合法, maxLen=4
right=4, c='B': freq={A:3,B:2}, maxFreq=3, len=5, 5-3=2>1 不合法！
  左边出窗 s[0]='A': freq={A:2,B:2}, left=1, maxFreq 保持 3 不变
  len=4 (right=4, left=1)，maxLen=4
right=5, c='B': freq={A:2,B:3}, maxFreq=3, len=5, 5-3=2>1 不合法！
  左边出窗 s[1]='A': freq={A:1,B:3}, left=2, maxFreq 保持 3 不变
  len=4, maxLen=4
right=6, c='A': freq={A:2,B:3}, maxFreq=3, len=5, 5-3=2>1 不合法！
  左边出窗 s[2]='B': freq={A:2,B:2}, left=3, maxFreq 保持 3 不变
  len=4, maxLen=4

最终 maxLen=4 ✓

---

第 4 章 从字符串到数组：思想的迁移

4.1 三道题的统一框架

回顾本篇三道题的共性：

题目	”坏元素”	合法条件	目标
1004 最大连续 1 III	0	zeros ⇐ k	最长窗口
1493 删掉一个元素后全为 1	0	zeros ⇐ 1，最后减 1	最长窗口
424 最长重复字符替换	非最高频字符	len - maxFreq ⇐ k	最长窗口

三道题用同一个抽象框架：“允许 $k$ 个坏元素的最长子区间”。区别只在于”坏元素”的定义：对于 1004/1493，坏元素就是 0；对于 424，坏元素是”需要被替换的字符”（即非最高频字符）。

4.2 衍生变体：可以替换 k 个数字的最长等差数列（思考题）

如果把 424 的条件从”字符全相同”改为”数字构成等差数列”，问题复杂度会大幅上升（因为等差数列的公差是动态确定的，不像字符可以用频率快速判断）。这说明 424 的可解性，很大程度上依赖于”合法条件只取决于最高频元素”这个特性。

4.3 当 maxFreq 需要精确维护时

424 能用”不更新 maxFreq”的技巧，是因为我们只关心答案（最大窗口长度），不需要精确追踪中间状态。

但如果题目需要计算所有合法窗口的总数（而不只是最大长度），这个技巧就不适用了。此时需要在出窗时精确更新 maxFreq：

// 精确维护 maxFreq：出窗时重新扫描 freq 数组
freq[s.charAt(left) - 'A']--;
left++;
maxFreq = 0;
for (int f : freq) maxFreq = Math.max(maxFreq, f);
// 时间复杂度 O(26n) = O(n)，但常数更大

---

第 5 章 面试中的注意事项

5.1 解释”不缩反扩”时的表达技巧

面试官可能对”为什么用 if 而不是 while”这个细节追问。推荐的回答框架：

1. 先说结论：“这道题只需要最大窗口长度，窗口大小不需要减小，所以用 if 足够”
2. 再说理由：“每次右指针前进，窗口大小最多 +1；不合法时 if 收缩一步，窗口大小回到原来；合法时窗口扩大。因此窗口大小单调不减，最终的最大值就是答案”
3. 补充 maxFreq 不回退的解释：“maxFreq 保持历史最高，是因为只有当某种字符的频率再次达到历史最高时，窗口才有机会扩张。让 maxFreq 过时（偏大），等价于设置了一个更高的门槛，确保窗口扩张时一定是真正的进步”

5.2 为什么此题用 if 而 LeetCode 76 用 while

• LeetCode 76 求最短：需要在合法时尽量收缩，找到最短的合法窗口，while 循环持续收缩直到不合法
• LeetCode 424 求最长：不合法时只需平移一步，窗口大小不减小，if 足够

这两道题的收缩逻辑恰好相反，是理解可变窗口”双模式”的绝佳对比。

5.3 延伸题目

• LeetCode 1208 尽可能使字符串相等：将 s 替换成 t，每次替换代价是 |s[i]-t[i]|，总代价不超过 maxCost，找最长子串。把”替换代价”换成了”代价预算”，与 1004 几乎同构。
• LeetCode 2401 最长优美子数组：限制子数组中任意两个元素按位与不为 0，是数组版的”多条件约束窗口”。

---

本篇总结

本篇围绕”允许 k 次替换/删除的最长连续子区间”这一类型，讲解了三道题：

1. LeetCode 1004：标准”至多 k 个坏元素”的最长窗口，while 收缩，最直接的可变窗口模板
2. LeetCode 1493：1004 的变体，“恰好删 1 个”转化为”至多 1 个 0”再减 1
3. LeetCode 424：最精妙的一题——maxFreq 不回退、用 if 替代 while，体现了”只关心最大值时可以维护历史最优而非当前精确值”的设计思想

核心结论：当题目只求最大窗口长度时，可以让窗口大小单调不减（平移而非收缩），并维护历史最优状态（如 maxFreq），这往往能简化代码逻辑，同时保证正确性。

---

参考与延伸

• 03 最小覆盖子串：可变窗口收缩条件的黄金法则 — 求最短窗口的对称逻辑
• 09 多类别元素与恰好 K 型窗口：高阶滑动窗口技法 — “恰好”与”至多”的系统转化

---

课后练习

LeetCode 2024 - 考试的最大困扰度（中等）

一位老师出了一份由若干 'T'（判断题）和 'F'（填空题）组成的试卷，可以将至多 k 道题改变为另一种题型，使得试卷中最长连续相同题型的子串尽可能长。

提示：对 'T' 和 'F' 分别跑一遍本篇的「坏元素」模板（'F' 是坏元素求最长 'T' 连续段，'T' 是坏元素求最长 'F' 连续段），取两次结果的最大值。与 LeetCode 1004 的模板完全相同，替换目标字符即可。