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

字数 2946 2025-12-11 14:24:24

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

问题描述
给定一个整数数组 nums 和一个整数 k。你可以执行最多 k 次操作，每次操作可以将数组中任意一个位置的元素替换成任意值。目标是：在最多替换 k 次的前提下，找到一个最长的连续子数组，使得这个子数组内所有元素相同。你需要返回这个最长长度。

示例：
输入：nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
输出：6
解释：将中间两个0替换为1，得到长度为6的全1子数组 [1,1,1,1,1,1,1,1,1,1,0] 中的前六个1。

解题过程

步骤1：问题转化与核心观察
我们并不是真的要替换元素，而是找这样一个子数组：在该子数组内，除了占多数的某个值（称为目标值）外，其他不同值的个数不超过 k。因为不同值可以通过替换变成目标值，从而让整个子数组变成同值。
因此，问题等价于：

找一个子数组，使得其中出现次数最多的元素的出现次数，加上 k，不小于子数组长度，且子数组尽可能长。

形式化：设子数组为 nums[left:right]，其长度为 len，其中元素 x 出现次数为 count(x)。我们要求存在某个 x 使得：

len - count(x) ≤ k

即：

len ≤ count(x) + k

我们希望 len 最大化。

步骤2：暴力思路
对于每个可能的子数组（O(n²) 个），统计其中每个数字的出现次数，找到最大出现次数 maxCount，检查 len - maxCount ≤ k 是否成立。复杂度 O(n³) 或 O(n²·C)，C 是数字种类数，不可接受。

步骤3：滑动窗口思路
这其实是一个经典的“最多替换k次的最长重复子串”问题，可以用滑动窗口高效解决，但为了符合区间DP的要求，我们故意用区间DP的思路来解，以锻炼DP思维。

区间DP定义：
dp[i][j] 表示子数组 nums[i..j] 在最多替换 k 次的情况下，能否变成全相同元素？但这样定义是布尔值，无法直接得到最长长度，而且状态数 O(n²)，转移复杂度高。

改进定义：
dp[i][j] 表示子数组 nums[i..j] 变成全相同元素所需的最小替换次数。
那么状态转移可以考虑：

如果 nums[i] == nums[j]，则 dp[i][j] 可以从 dp[i+1][j-1] 转移来，但要注意中间部分可能和两端不同，需要统计中间有多少不同于 nums[i] 的数。
一般情况下，我们需要枚举分割点，但这样复杂度 O(n³)，会超时。

但本题的滑动窗口解法是更优的，我们这里用DP思路是为了理解区间DP的另一种建模方式：枚举目标值。

步骤4：按目标值分别DP
由于最终子数组会变成某个值 val，我们可以对每个可能的值单独考虑。
对于固定的值 val，问题变成：

在数组中找一个最长子数组，其中非 val 的元素个数不超过 k。

这就是一个简单的滑动窗口问题：用双指针 left 和 right 遍历，维护窗口内非 val 的个数 notVal，当 notVal > k 时移动左指针，过程中记录最大窗口长度。

步骤5：算法步骤

找出数组中所有不同的值（或者为了简便，我们只考虑数组中出现的值）。
对每个值 val：
- 初始化 left = 0, notVal = 0, maxLen = 0
- 遍历右指针 right 从 0 到 n-1：
  - 如果 nums[right] != val，则 notVal += 1
  - 当 notVal > k 时：
    - 如果 nums[left] != val，则 notVal -= 1
    - left += 1
  - 更新 maxLen = max(maxLen, right - left + 1)
所有 val 中得到的最大 maxLen 就是答案。

步骤6：复杂度

如果枚举所有可能的值（比如数字范围有限），则复杂度 O(M * n)，M 是值的种类数。
实际上，我们只需要枚举数组中出现的值，因为不出现的值不可能成为最终子数组的值（除非全数组替换，但那样长度就是 n 但受限于 k）。
最坏情况是所有值都不同，则 M = n，复杂度 O(n²)。

步骤7：进一步优化
其实可以一次遍历得到答案，不需要枚举 val。我们可以用如下方法：

维护一个哈希表 count 记录窗口内每个值的出现次数。
同时维护窗口内出现次数的最大值 maxCount。
窗口合法的条件是：窗口长度 - maxCount ≤ k。
当不合法时，移动左指针并更新 count 和 maxCount。

这是因为，我们要让窗口内某个值出现次数尽可能多，替换的次数就少。所以维护出现次数的最大值即可。

具体：

初始化 left = 0, maxCount = 0, 哈希表 count 全0。
遍历 right 从 0 到 n-1：
- count[nums[right]] += 1
- maxCount = max(maxCount, count[nums[right]])
- 如果 (right - left + 1) - maxCount > k：
  - count[nums[left]] -= 1
  - left += 1
- 更新答案 ans = max(ans, right - left + 1)
返回 ans。

注意：maxCount 不需要在左指针移动时重新计算，因为即使它变小了，窗口长度也变小了，不会让答案更大，所以保持历史最大值不影响结果。

步骤8：例子验证
nums = [1,1,1,0,0,0,1,1,1,1,0], k=2

右指针移动过程（简化）：

right=0, val=1, count[1]=1, maxCount=1, len=1, ok
right=1, val=1, count[1]=2, maxCount=2, len=2, ok
right=2, val=1, count[1]=3, maxCount=3, len=3, ok
right=3, val=0, count[0]=1, maxCount=3, len=4, 4-3=1≤2, ok
right=4, val=0, count[0]=2, maxCount=3, len=5, 5-3=2≤2, ok
right=5, val=0, count[0]=3, maxCount=3, len=6, 6-3=3>2 → 移动左指针：
- left=0, val=1, count[1]=2, left=1, len=5, 5-3=2≤2, ok
继续... 最终得到最大长度6。

步骤9：总结
这个问题本质是一个“最多替换k次的最长重复子数组”，滑动窗口解法是最优的，时间复杂度 O(n)，空间复杂度 O(值域)。区间DP虽然可以建模，但不如滑动窗口高效。核心是维护窗口内最大频次，使得窗口长度减去最大频次不超过k。

最长同值子数组的最大长度问题（进阶：允许最多替换K次元素）问题描述给定一个整数数组 nums 和一个整数 k 。你可以执行最多 k 次操作，每次操作可以将数组中任意一个位置的元素替换成任意值。目标是：在最多替换 k 次的前提下，找到一个最长的连续子数组，使得这个子数组内所有元素相同。你需要返回这个最长长度。示例：输入：nums = [ 1,1,1,0,0,0,1,1,1,1,0 ], k = 2 输出：6 解释：将中间两个0替换为1，得到长度为6的全1子数组 [ 1,1,1,1,1,1,1,1,1,1,0 ] 中的前六个1。解题过程步骤1：问题转化与核心观察我们并不是真的要替换元素，而是找这样一个子数组：在该子数组内，除了占多数的某个值（称为目标值）外，其他不同值的个数不超过 k 。因为不同值可以通过替换变成目标值，从而让整个子数组变成同值。因此，问题等价于：找一个子数组，使得其中出现次数最多的元素的出现次数，加上 k ，不小于子数组长度，且子数组尽可能长。形式化：设子数组为 nums[left:right] ，其长度为 len ，其中元素 x 出现次数为 count(x) 。我们要求存在某个 x 使得：即：我们希望 len 最大化。步骤2：暴力思路对于每个可能的子数组（O(n²) 个），统计其中每个数字的出现次数，找到最大出现次数 maxCount，检查 len - maxCount ≤ k 是否成立。复杂度 O(n³) 或 O(n²·C)，C 是数字种类数，不可接受。步骤3：滑动窗口思路这其实是一个经典的“最多替换k次的最长重复子串”问题，可以用滑动窗口高效解决，但为了符合区间DP的要求，我们故意用区间DP的思路来解，以锻炼DP思维。区间DP定义： dp[i][j] 表示子数组 nums[i..j] 在最多替换 k 次的情况下，能否变成全相同元素？但这样定义是布尔值，无法直接得到最长长度，而且状态数 O(n²)，转移复杂度高。改进定义： dp[i][j] 表示子数组 nums[i..j] 变成全相同元素所需的最小替换次数。那么状态转移可以考虑：如果 nums[i] == nums[j] ，则 dp[i][j] 可以从 dp[i+1][j-1] 转移来，但要注意中间部分可能和两端不同，需要统计中间有多少不同于 nums[i] 的数。一般情况下，我们需要枚举分割点，但这样复杂度 O(n³)，会超时。但本题的滑动窗口解法是更优的，我们这里用DP思路是为了理解区间DP的另一种建模方式：枚举目标值。步骤4：按目标值分别DP 由于最终子数组会变成某个值 val ，我们可以对每个可能的值单独考虑。对于固定的值 val ，问题变成：在数组中找一个最长子数组，其中非 val 的元素个数不超过 k 。这就是一个简单的滑动窗口问题：用双指针 left 和 right 遍历，维护窗口内非 val 的个数 notVal ，当 notVal > k 时移动左指针，过程中记录最大窗口长度。步骤5：算法步骤找出数组中所有不同的值（或者为了简便，我们只考虑数组中出现的值）。对每个值 val ：初始化 left = 0 , notVal = 0 , maxLen = 0 遍历右指针 right 从 0 到 n-1：如果 nums[right] != val ，则 notVal += 1 当 notVal > k 时：如果 nums[left] != val ，则 notVal -= 1 left += 1 更新 maxLen = max(maxLen, right - left + 1) 所有 val 中得到的最大 maxLen 就是答案。步骤6：复杂度如果枚举所有可能的值（比如数字范围有限），则复杂度 O(M * n)，M 是值的种类数。实际上，我们只需要枚举数组中出现的值，因为不出现的值不可能成为最终子数组的值（除非全数组替换，但那样长度就是 n 但受限于 k）。最坏情况是所有值都不同，则 M = n，复杂度 O(n²)。步骤7：进一步优化其实可以一次遍历得到答案，不需要枚举 val 。我们可以用如下方法：维护一个哈希表 count 记录窗口内每个值的出现次数。同时维护窗口内出现次数的最大值 maxCount 。窗口合法的条件是：窗口长度 - maxCount ≤ k 。当不合法时，移动左指针并更新 count 和 maxCount 。这是因为，我们要让窗口内某个值出现次数尽可能多，替换的次数就少。所以维护出现次数的最大值即可。具体：初始化 left = 0 , maxCount = 0 , 哈希表 count 全0。遍历 right 从 0 到 n-1： count[nums[right]] += 1 maxCount = max(maxCount, count[nums[right]]) 如果 (right - left + 1) - maxCount > k ： count[nums[left]] -= 1 left += 1 更新答案 ans = max(ans, right - left + 1) 返回 ans 。注意： maxCount 不需要在左指针移动时重新计算，因为即使它变小了，窗口长度也变小了，不会让答案更大，所以保持历史最大值不影响结果。步骤8：例子验证 nums = [ 1,1,1,0,0,0,1,1,1,1,0 ], k=2 右指针移动过程（简化）： right=0, val=1, count[ 1 ]=1, maxCount=1, len=1, ok right=1, val=1, count[ 1 ]=2, maxCount=2, len=2, ok right=2, val=1, count[ 1 ]=3, maxCount=3, len=3, ok right=3, val=0, count[ 0 ]=1, maxCount=3, len=4, 4-3=1≤2, ok right=4, val=0, count[ 0 ]=2, maxCount=3, len=5, 5-3=2≤2, ok right=5, val=0, count[ 0 ]=3, maxCount=3, len=6, 6-3=3>2 → 移动左指针： left=0, val=1, count[ 1 ]=2, left=1, len=5, 5-3=2≤2, ok 继续... 最终得到最大长度6。步骤9：总结这个问题本质是一个“最多替换k次的最长重复子数组”，滑动窗口解法是最优的，时间复杂度 O(n)，空间复杂度 O(值域)。区间DP虽然可以建模，但不如滑动窗口高效。核心是维护窗口内最大频次，使得窗口长度减去最大频次不超过k。