最长同值子数组的最大长度问题（允许最多替换K次元素）

题目描述

给定一个整数数组 nums 和一个整数 k。你最多可以对数组进行 k 次操作，每次操作可以将数组中任意一个元素替换成任意另一个整数。请问，在进行最多 k 次替换后，数组中由相同元素组成的、连续的、最长子数组的长度是多少？

例如：

• 输入：nums = [1,1,1,0,0,1,1,0,1,1], k = 2
• 输出：7
• 解释：可以将两个 0 替换成 1，得到子数组 [1,1,1,1,1,1,1]（索引0到6），长度为7。

解题思路

这个问题可以转化为：寻找一个最长的连续子数组，使得在子数组中，将出现次数最多的元素保留，其余元素通过替换操作变成这个元素，并且替换的次数不超过 k。

核心思想是使用滑动窗口（双指针）来遍历所有可能的子数组，但为了深入理解区间动态规划（DP）的思路，我们可以先思考如何用DP来定义状态，并发现其低效性，从而引出更优的滑动窗口解法。本题的讲解重点在于如何从区间DP的思路转换到滑动窗口的优化。

步骤1：暴力法与区间DP的初步设想

最直接的想法是枚举所有子数组 [i, j]，对于每个子数组，统计其中各个数字出现的频率，找出频率最高的数字 maxFreq，那么将子数组内其他数字都替换成这个数字所需的操作次数为 (j - i + 1) - maxFreq。如果这个操作次数 <= k，那么这个子数组就是可行的，其长度是 j - i + 1。我们取所有可行子数组的最大长度即可。

伪代码逻辑：

maxLen = 0
for i in 0 to n-1:
    for j in i to n-1:
        统计子数组 nums[i..j] 中每个数字出现的次数
        找出最大出现次数 maxFreq
        如果 (j - i + 1) - maxFreq <= k:
            maxLen = max(maxLen, j - i + 1)

这个算法的时间复杂度是 O(n³)（统计频率需要O(n)），显然太低效。

步骤2：尝试用区间DP优化

一个自然的区间DP想法是定义 dp[i][j] 为子数组 nums[i..j] 在最多 k 次替换下能得到的最大同值长度。但这样定义状态会有一个问题：dp[i][j] 的值可能与子数组内具体的数字分布以及已经使用的替换次数有关，状态维度不够。如果增加状态维度，比如 dp[i][j][t] 表示在子数组 i..j 中，最多使用 t 次替换能得到的最长同值长度，但状态转移会非常复杂，因为我们需要考虑保留哪个数字作为最终的同值元素。这会导致状态转移需要枚举保留的数字，时间复杂度很高，不优于滑动窗口。

因此，对于这个“最多替换K次”的问题，滑动窗口是更自然、更高效的解法。但我们可以从区间覆盖的角度来理解滑动窗口。

步骤3：滑动窗口（双指针）解法详解

我们可以将问题重新表述为：寻找一个最长的子数组，使得在子数组中，除了出现次数最多的那个数字，其余数字的个数不超过 k（因为其余数字都需要被替换成那个最多出现的数字）。

滑动窗口的思路：

1. 用两个指针 left 和 right 定义一个窗口 [left, right]。
2. 用一个哈希表（或数组，如果数字范围已知）freq 来记录窗口内各个数字出现的次数。
3. 我们维护窗口内出现次数的最大值 maxFreq。
4. 在每一步，我们扩展右指针 right，将 nums[right] 加入窗口，更新 freq 和 maxFreq。
5. 计算当前窗口的长度 winLen = right - left + 1。如果 winLen - maxFreq > k，意味着当前窗口内，将非主要数字替换成主要数字所需的操作次数超过了 k。这时我们需要缩小窗口：移动左指针 left，并从 freq 中减少 nums[left] 的计数（注意，减少后 maxFreq 可能需要更新，但我们可以用一个技巧：不显式更新 maxFreq，因为即使 maxFreq 变小了，它只会让条件更严格，不会导致误判满足条件，而且我们只关心最大长度，maxFreq 的减小不会影响我们记录到的历史最大窗口长度）。
6. 在每一步，记录窗口的最大长度。

关键点：

• 为什么在 winLen - maxFreq > k 时缩小窗口是安全的？因为如果当前窗口不满足条件，任何包含当前窗口的更大窗口肯定也不满足条件（因为需要替换的数字只会更多），所以我们可以安全地移动左指针来尝试寻找新的可行窗口。
• 为什么我们不需要在缩小窗口时更新 maxFreq？因为我们关心的其实是“历史上窗口内出现过的最大频率”，这个频率可能对应着之前窗口中的某个数字。即使左指针移动导致某个数字的频率下降，maxFreq 可能比实际当前窗口的最大频率大，但这不会导致错误。因为如果使用一个较大的 maxFreq 去判断条件 winLen - maxFreq > k，条件会更严格（更容易不满足），这只会让我们更早地缩小窗口，但不会错过更长的窗口（因为更长的窗口必须满足条件，而用旧的、更大的 maxFreq 去判断，条件更宽松，实际上如果旧的 maxFreq 还满足，那肯定没问题；如果不满足，我们缩小窗口是正确的）。而且，我们最终记录的是窗口的最大长度，只要我们在窗口有效时记录即可。

步骤4：算法步骤

1. 初始化 left = 0, maxFreq = 0, 哈希表 freq 为空，maxLen = 0。
2. 遍历右指针 right 从 0 到 n-1：
   a. 将 nums[right] 加入 freq，并更新 maxFreq = max(maxFreq, freq[nums[right]])。
   b. 计算当前窗口长度 winLen = right - left + 1。
   c. 如果 winLen - maxFreq > k，则当前窗口无效，需要缩小：将 nums[left] 从 freq 中减去1，并将 left 右移一位。
   d. 更新 maxLen = max(maxLen, right - left + 1)。
3. 返回 maxLen。

步骤5：举例说明

以 nums = [1,1,1,0,0,1,1,0,1,1], k=2 为例。

• 初始化：left=0, maxFreq=0, maxLen=0
• right=0: nums[0]=1, freq{1:1}, maxFreq=1, winLen=1, 1-1=0<=2, 有效，maxLen=1
• right=1: nums[1]=1, freq{1:2}, maxFreq=2, winLen=2, 2-2=0<=2, 有效，maxLen=2
• right=2: nums[2]=1, freq{1:3}, maxFreq=3, winLen=3, 3-3=0<=2, 有效，maxLen=3
• right=3: nums[3]=0, freq{1:3,0:1}, maxFreq=3, winLen=4, 4-3=1<=2, 有效，maxLen=4
• right=4: nums[4]=0, freq{1:3,0:2}, maxFreq=3, winLen=5, 5-3=2<=2, 有效，maxLen=5
• right=5: nums[5]=1, freq{1:4,0:2}, maxFreq=4, winLen=6, 6-4=2<=2, 有效，maxLen=6
• right=6: nums[6]=1, freq{1:5,0:2}, maxFreq=5, winLen=7, 7-5=2<=2, 有效，maxLen=7
• right=7: nums[7]=0, freq{1:5,0:3}, maxFreq=5, winLen=8, 8-5=3>2, 无效 -> 缩小窗口：left=0, freq{1:4,0:3}, left=1, 此时 winLen=7, 7-5=2<=2? 注意：maxFreq 还是5，实际上当前窗口 freq{1:4,0:3} 的最大频率是4，但我们仍用5计算，7-5=2<=2，条件满足，记录 maxLen=7（实际上窗口是[1,7]长度7）。这里体现了不更新maxFreq不会导致错误，因为计算出的条件仍然满足（2<=2）。
• 继续移动 right=8,9... 但窗口长度不会超过7。

最终结果为7。

步骤6：复杂度分析

• 时间复杂度：O(n)，其中 n 是数组长度。每个元素最多被左指针和右指针各访问一次。
• 空间复杂度：O(m)，其中 m 是数组中不同数字的个数，用于哈希表存储频率。

总结

本题虽然可以用区间DP的思路去思考，但最优解法是滑动窗口。其核心在于维护一个窗口，使得窗口内“非主要数字”的个数不超过 k。通过动态调整窗口边界，我们可以在 O(n) 时间内找到最长的满足条件的子数组。这个技巧在很多“最多改变K次”或“最多包含K个不同字符”的问题中都很常见。