区间动态规划例题：最长同值子数组问题（最多替换K次元素）

题目描述
给定一个整数数组 nums 和一个整数 k。你可以将数组中最多 k 个元素替换成任意整数。替换操作可以在数组的任何位置进行。你的目标是：在最多进行 k 次替换后，找出数组中最长的连续子数组，使得这个子数组中的所有元素都相同（即子数组内所有值相等）。返回这个最长子数组的长度。

示例
输入：nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
输出：6
解释：可以将中间的两个 0 替换为 1（或者将开头的两个 1 替换为 0），得到 [1,1,1,1,1,1,1,1,1,1,0] 或 [0,0,0,0,0,0,1,1,1,1,0]，其中最长的全 1 子数组长度为 6。

解题思路
这个问题可以通过滑动窗口高效解决，但为了深入理解区间动态规划，我们可以先用区间DP来思考，再过渡到更优解法。

为什么用区间DP思考？
区间动态规划通常用于处理“区间”性质的问题，比如对区间进行划分、合并、染色等。这个问题本质是寻找一个区间，通过替换其中最多 k 个元素，使得整个区间内元素相同。如果我们定义 dp[i][j] 为子数组 nums[i..j] 在最多 k 次替换下能变成全相同值的最小替换次数，那么问题就变成：找到所有满足 dp[i][j] <= k 的区间中，长度 (j-i+1) 的最大值。

难点：区间DP直接计算复杂度为 O(n² * 状态)，但我们可以借助“频数统计”来优化。

详细解题步骤

步骤1：问题转化
对于任意区间 [l, r]，设其长度为 len = r - l + 1，区间内出现次数最多的数字的出现次数为 maxFreq。
那么，要将区间内所有数字都变成这个出现最多的数字，最少需要的替换次数 = len - maxFreq。
这是因为：出现次数最多的数字不需要改变，只需要将其他数字改成它即可。
因此，如果 len - maxFreq <= k，那么这个区间就是可行的（可以通过最多 k 次替换变成全相同值）。

步骤2：暴力枚举区间
我们可以枚举所有区间 [l, r]，并统计区间内出现次数最多的数字的频次 maxFreq，然后检查是否满足 len - maxFreq <= k。
时间复杂度：枚举区间 O(n²)，统计频次 O(n) 或 O(1)（用哈希表动态更新），总复杂度 O(n²) 或 O(n³) 取决于实现。
空间复杂度：O(n) 用于哈希表。

步骤3：滑动窗口优化
实际上，我们不需要枚举所有区间，因为这是一个“最长满足条件的子数组”问题，适合用滑动窗口（双指针）来在线性时间内解决。

• 维护一个窗口 [left, right]，并用一个哈希表 freq 记录窗口内每个数字出现的次数，同时记录窗口内出现次数的最大值 maxFreq。
• 不断右移 right 指针，将 nums[right] 加入窗口，更新 freq 和 maxFreq。
• 检查当前窗口是否满足条件：窗口长度 (right - left + 1) - maxFreq <= k。如果不满足，说明即使将窗口内其他数字都改成出现最多的数字，也需要超过 k 次替换，此时需要缩小窗口：左移 left 指针，并更新 freq 和 maxFreq。
• 在整个过程中，记录窗口的最大长度即为答案。

为什么可以这样优化？
关键在于，当右移 right 时，maxFreq 只会增加或保持不变，不会减少。但左移 left 时，maxFreq 可能减少，不过我们不需要实时更新 maxFreq 的精确值，因为我们只需要保证“当前窗口长度 - 当前记录的 maxFreq > k” 时才移动左指针。实际上，我们可以用“历史最大值”来作为 maxFreq，因为即使左移导致某个数字的频次减少，但历史最大值可能仍然是之前较大的值，这只会让条件更严格，不会导致结果错误（因为我们要找最大窗口，所以用历史最大值是安全的）。

步骤4：算法实现

输入：数组 nums，整数 k
初始化 left = 0, maxFreq = 0, ans = 0
初始化哈希表 freq
for right in [0, n-1]:
    freq[nums[right]] += 1
    maxFreq = max(maxFreq, freq[nums[right]])
    如果 (right - left + 1) - maxFreq > k:
        # 窗口不符合条件，左移
        freq[nums[left]] -= 1
        left += 1
    否则：
        ans = max(ans, right - left + 1)
返回 ans

步骤5：举例验证
以 nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2 为例：

• right=0: 窗口[1], freq={1:1}, maxFreq=1, len-maxFreq=0<=k, ans=1
• right=1: 窗口[1,1], freq={1:2}, maxFreq=2, len-maxFreq=0<=k, ans=2
• ... 直到 right=5: 窗口[1,1,1,0,0,0], freq={1:3,0:3}, maxFreq=3, len-maxFreq=3>k → 移动 left
  left=0 → 窗口[1,1,0,0,0], freq={1:2,0:3}, maxFreq=3, len-maxFreq=2<=k → ans=5
• 继续右移 right，最终找到最大窗口长度为 6。

步骤6：复杂度分析
时间复杂度：O(n)，每个元素最多被左指针和右指针访问一次。
空间复杂度：O(n)，用于哈希表存储频次。

与区间DP的联系
虽然滑动窗口是最优解，但我们可以从区间DP的角度理解：
定义 dp[l][r] 为将区间 [l, r] 变为全相同值所需的最小替换次数。
状态转移：dp[l][r] = min(dp[l][r-1], dp[l+1][r]) + 1，但这忽略了区间内数字的分布。实际上，dp[l][r] = (r-l+1) - maxFreq(l, r)，其中 maxFreq(l, r) 是区间内出现最多的数字的频次。
所以，问题转化为：求所有满足 (r-l+1) - maxFreq(l, r) <= k 的最大区间长度。
滑动窗口高效地解决了这个最值问题。

总结
这个题目本质是一个“最多替换K次的最长连续相同子数组”问题。

• 核心思路：对于任意区间，最小替换次数 = 区间长度 - 区间内出现最多的数字的频次。
• 最优解法：滑动窗口，维护窗口内频次哈希表和最大频次，线性时间内找到最大窗口。
• 区间DP视角：状态定义为区间的最小替换次数，但直接DP效率低，滑动窗口巧妙地利用双指针和频次统计避免了区间枚举。