Hard

题目描述

给你一个整数数组 nums 和两个整数 x 和 k。你可以执行以下操作任意次数（包括零次）：

  • 将 nums 的任意元素增加或减少 1。

返回使 nums 中至少有 k 个非重叠且大小恰好为 x 的子数组，其中每个子数组内的所有元素都相等所需的最少操作次数。

示例 1：

输入：nums = [5,-2,1,3,7,3,6,4,-1], x = 3, k = 2
输出：8
解释：
- 使用 3 次操作给 nums[1] 加 3，使用 2 次操作给 nums[3] 减 2。结果数组为 [5, 1, 1, 1, 7, 3, 6, 4, -1]。
- 使用 1 次操作给 nums[5] 加 1，使用 2 次操作给 nums[6] 减 2。结果数组为 [5, 1, 1, 1, 7, 4, 4, 4, -1]。
- 现在，子数组 [1, 1, 1]（从索引 1 到 3）和 [4, 4, 4]（从索引 5 到 7）内的所有元素都相等。总共使用了 8 次操作，所以输出是 8。

示例 2：

输入：nums = [9,-2,-2,-2,1,5], x = 2, k = 2
输出：3
解释：
- 使用 3 次操作给 nums[4] 减 3。结果数组为 [9, -2, -2, -2, -2, 5]。
- 现在，子数组 [-2, -2]（从索引 1 到 2）和 [-2, -2]（从索引 3 到 4）内的所有元素都相等。总共使用了 3 次操作，所以输出是 3。

约束条件：

  • 2 <= nums.length <= 10^5
  • -10^6 <= nums[i] <= 10^6
  • 2 <= x <= nums.length
  • 1 <= k <= 15
  • 2 <= k * x <= nums.length

解题思路

这道题的核心思路是动态规划结合贪心选择。

关键观察：

  1. 要使一个长度为 x 的窗口内所有元素相等，最优策略是将所有元素都调整为该窗口的中位数，这样总操作次数最少。
  2. 题目要求选择 k 个非重叠的子数组，这是一个典型的区间选择问题。

算法步骤：

  1. 预处理阶段：对于每个可能的长度为 x 的窗口，计算将该窗口内所有元素调整为中位数所需的操作次数。
  2. 动态规划：设 dp[i][j] 表示在前 i 个位置中选择 j 个非重叠窗口的最小操作次数。
  3. 状态转移：对于每个位置 i，我们可以选择：
    • 不在位置 i 结束窗口：dp[i][j] = dp[i-1][j]
    • 在位置 i 结束一个窗口：dp[i][j] = min(dp[i][j], dp[i-x][j-1] + cost[i-x+1])

实现细节：

  • 计算中位数的操作次数时，先对窗口元素排序，然后计算所有元素到中位数的距离和。
  • 使用滚动数组优化空间复杂度。
  • 注意边界条件的处理。

这种方法时间复杂度为 O(n²k + nx log x)，在给定约束下可以高效解决问题。

代码实现

class Solution {
public:
    long long minOperations(vector<int>& nums, int x, int k) {
        int n = nums.size();
        vector<long long> cost(n - x + 1);
        
        // 预计算每个窗口的代价
        for (int i = 0; i <= n - x; i++) {
            vector<int> window(nums.begin() + i, nums.begin() + i + x);
            sort(window.begin(), window.end());
            int median = window[x / 2];
            long long windowCost = 0;
            for (int val : window) {
                windowCost += abs(val - median);
            }
            cost[i] = windowCost;
        }
        
        // dp[i][j] 表示前i个位置选择j个窗口的最小代价
        vector<vector<long long>> dp(n + 1, vector<long long>(k + 1, LLONG_MAX));
        dp[0][0] = 0;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                // 不选择以i结尾的窗口
                dp[i][j] = dp[i-1][j];
                
                // 选择以i结尾的窗口
                if (j > 0 && i >= x && dp[i-x][j-1] != LLONG_MAX) {
                    dp[i][j] = min(dp[i][j], dp[i-x][j-1] + cost[i-x]);
                }
            }
        }
        
        return dp[n][k];
    }
};

class Solution:
    def minOperations(self, nums: List[int], x: int, k: int) -> int:
        n = len(nums)
        cost = [0] * (n - x + 1)
        
        # 预计算每个窗口的代价
        for i in range(n - x + 1):
            window = sorted(nums[i:i + x])
            median = window[x // 2]
            cost[i] = sum(abs(val - median) for val in window)
        
        # dp[i][j] 表示前i个位置选择j个窗口的最小代价
        dp = [[float('inf')] * (k + 1) for _ in range(n + 1)]
        dp[0][0] = 0
        
        for i in range(1, n + 1):
            for j in range(k + 1):
                # 不选择以i结尾的窗口
                dp[i][j] = dp[i-1][j]
                
                # 选择以i结尾的窗口
                if j > 0 and i >= x and dp[i-x][j-1] != float('inf'):
                    dp[i][j] = min(dp[i][j], dp[i-x][j-1] + cost[i-x])
        
        return dp[n][k]

public class Solution {
    public long MinOperations(int[] nums, int x, int k) {
        int n = nums.Length;
        long[] cost = new long[n - x + 1];
        
        // 预计算每个窗口的代价
        for (int i = 0; i <= n - x; i++) {
            int[] window = new int[x];
            Array.Copy(nums, i, window, 0, x);
            Array.Sort(window);
            int median = window[x / 2];
            long windowCost = 0;
            foreach (int val in window) {
                windowCost += Math.Abs(val - median);
            }
            cost[i] = windowCost;
        }
        
        // dp[i][j] 表示前i个位置选择j个窗口的最小代价
        long[,] dp = new long[n + 1, k + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                dp[i, j] = long.MaxValue;
            }
        }
        dp[0, 0] = 0;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                // 不选择以i结尾的窗口
                dp[i, j] = dp[i-1, j];
                
                // 选择以i结尾的窗口
                if (j > 0 && i >= x && dp[i-x, j-1] != long.MaxValue) {
                    dp[i, j] = Math.Min(dp[i, j], dp[i-x, j-1] + cost[i-x]);
                }
            }
        }
        
        return dp[n, k];
    }
}

var minOperations = function(nums, x, k) {
    const n = nums.length;
    const cost = new Array(n - x + 1);
    
    // 预计算每个窗口的代价
    for (let i = 0; i <= n - x; i++) {
        const window = nums.slice(i, i + x).sort((a, b) => a - b);
        const median = window[Math.floor(x / 2)];
        let windowCost = 0;
        for (const val of window) {
            windowCost += Math.abs(val - median);
        }
        cost[i] = windowCost;
    }
    
    // dp[i][j] 表示前i个位置选择j个窗口的最小代价
    const dp = Array(n + 1).fill(null).map(() => Array(k + 1).fill(Infinity));
    dp[0][0] = 0;
    
    for (let i = 1; i <= n; i++) {
        for (let j = 0; j <= k; j++) {
            // 不选择以i结尾的窗口
            dp[i][j] = dp[i-1][j];
            
            // 选择以i结尾的窗口
            if (j > 0 && i >= x && dp[i-x][j-1] !== Infinity) {
                dp[i][j] = Math.min(dp[i][j], dp[i-x][j-1] + cost[i-x]);
            }
        }
    }
    
    return dp[n][k];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n²k + nx log x)预处理窗口代价需要 O(nx log x)，动态规划需要 O(n²k)
空间复杂度O(nk)存储动态规划状态和窗口代价数组

相关题目