Medium

题目描述

你正在设计一个动态数组。给你一个下标从 0 开始的整数数组 nums，其中 nums[i] 是第 i 时刻数组中的元素数量。另给你一个整数 k，表示你可以 调整 数组大小的 最多 次数（每次都可以调整到任意大小）。

t 时刻数组的大小 sizet 必须大于等于 nums[t]，因为数组需要有足够的空间容纳所有元素。t 时刻 浪费的空间 定义为 sizet - nums[t]，总浪费空间 为在每个时刻 t（0 <= t < nums.length）浪费的空间之和。

在 最多 进行 k 次调整数组大小的操作后，返回 最小总浪费空间。

**注意：**数组最开始时可以为任意大小，不计入调整次数。

示例 1：

输入：nums = [10,20], k = 0
输出：10
解释：size = [20,20]
我们可以让数组初始大小为 20。
总浪费空间为 (20 - 10) + (20 - 20) = 10。

示例 2：

输入：nums = [10,20,30], k = 1
输出：10
解释：size = [20,20,30]
我们可以让数组初始大小为 20，然后在时刻 2 调整大小为 30。
总浪费空间为 (20 - 10) + (20 - 20) + (30 - 30) = 10。

示例 3：

输入：nums = [10,20,15,30,20], k = 2
输出：15
解释：size = [10,20,20,30,30]
我们可以让数组初始大小为 10，在时刻 1 调整大小为 20，在时刻 3 调整大小为 30。
总浪费空间为 (10 - 10) + (20 - 20) + (20 - 15) + (30 - 30) + (30 - 20) = 15。

提示：

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 10^6
  • 0 <= k <= nums.length - 1

解题思路

这是一个经典的动态规划问题。关键观察是：对于任意连续区间，如果不进行调整操作，最优策略是将数组大小设为该区间内的最大值。

解题思路：

  1. 预处理计算区间浪费空间：对于任意区间 [i, j]，如果不调整大小，数组大小应设为 max(nums[i:j+1])，浪费空间为 maxVal * (j-i+1) - sum(nums[i:j+1])。

  2. 状态定义：dp[i][j] 表示处理前 i 个元素，使用 j 次调整操作的最小浪费空间。

  3. 状态转移：对于每个位置 i 和操作次数 j，我们可以选择在某个位置 p 进行最后一次调整，那么：

    • 区间 [p, i-1] 不进行调整，浪费空间为预计算的值
    • 前 p 个元素使用 j-1 次调整操作

  4. 边界条件：

    • dp[0][0] = 0（没有元素，没有操作，浪费为0）
    • 第一种情况：不使用任何调整操作时的浪费空间

优化技巧：

  • 使用前缀和快速计算区间和
  • 预计算所有可能区间的最大值和浪费空间
  • 状态转移时枚举最后一段区间的起始位置

时间复杂度为 O(n³)，空间复杂度为 O(n²)，对于题目约束（n ≤ 200）完全可行。

代码实现

class Solution {
public:
    int minSpaceWastedKResizing(vector<int>& nums, int k) {
        int n = nums.size();
        
        // 预计算区间浪费空间
        vector<vector<int>> waste(n, vector<int>(n));
        for (int i = 0; i < n; i++) {
            int maxVal = nums[i];
            int sum = nums[i];
            waste[i][i] = 0;
            for (int j = i + 1; j < n; j++) {
                maxVal = max(maxVal, nums[j]);
                sum += nums[j];
                waste[i][j] = maxVal * (j - i + 1) - sum;
            }
        }
        
        // dp[i][j] 表示前i个元素用j次调整的最小浪费
        vector<vector<int>> dp(n + 1, vector<int>(k + 1, INT_MAX));
        dp[0][0] = 0;
        
        for (int i = 1; i <= n; i++) {
            // 不使用任何调整操作
            dp[i][0] = waste[0][i - 1];
            
            // 使用j次调整操作
            for (int j = 1; j <= min(i - 1, k); j++) {
                for (int p = j; p < i; p++) {
                    if (dp[p][j - 1] != INT_MAX) {
                        dp[i][j] = min(dp[i][j], dp[p][j - 1] + waste[p][i - 1]);
                    }
                }
            }
        }
        
        int result = dp[n][0];
        for (int j = 1; j <= k; j++) {
            result = min(result, dp[n][j]);
        }
        
        return result;
    }
};

class Solution:
    def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:
        n = len(nums)
        
        # 预计算区间浪费空间
        waste = [[0] * n for _ in range(n)]
        for i in range(n):
            max_val = nums[i]
            sum_val = nums[i]
            waste[i][i] = 0
            for j in range(i + 1, n):
                max_val = max(max_val, nums[j])
                sum_val += nums[j]
                waste[i][j] = max_val * (j - i + 1) - sum_val
        
        # 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):
            # 不使用任何调整操作
            dp[i][0] = waste[0][i - 1]
            
            # 使用j次调整操作
            for j in range(1, min(i, k + 1)):
                for p in range(j, i):
                    if dp[p][j - 1] != float('inf'):
                        dp[i][j] = min(dp[i][j], dp[p][j - 1] + waste[p][i - 1])
        
        result = dp[n][0]
        for j in range(1, k + 1):
            result = min(result, dp[n][j])
        
        return result

public class Solution {
    public int MinSpaceWastedKResizing(int[] nums, int k) {
        int n = nums.Length;
        
        // 预计算区间浪费空间
        int[,] waste = new int[n, n];
        for (int i = 0; i < n; i++) {
            int maxVal = nums[i];
            int sum = nums[i];
            waste[i, i] = 0;
            for (int j = i + 1; j < n; j++) {
                maxVal = Math.Max(maxVal, nums[j]);
                sum += nums[j];
                waste[i, j] = maxVal * (j - i + 1) - sum;
            }
        }
        
        // dp[i,j] 表示前i个元素用j次调整的最小浪费
        int[,] dp = new int[n + 1, k + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                dp[i, j] = int.MaxValue;
            }
        }
        dp[0, 0] = 0;
        
        for (int i = 1; i <= n; i++) {
            // 不使用任何调整操作
            dp[i, 0] = waste[0, i - 1];
            
            // 使用j次调整操作
            for (int j = 1; j <= Math.Min(i - 1, k); j++) {
                for (int p = j; p < i; p++) {
                    if (dp[p, j - 1] != int.MaxValue) {
                        dp[i, j] = Math.Min(dp[i, j], dp[p, j - 1] + waste[p, i - 1]);
                    }
                }
            }
        }
        
        int result = dp[n, 0];
        for (int j = 1; j <= k; j++) {
            result = Math.Min(result, dp[n, j]);
        }
        
        return result;
    }
}

var minSpaceWastedKResizing = function(nums, k) {
    const n = nums.length;
    
    // 预计算区间浪费空间
    const waste = Array(n).fill(null).map(() => Array(n).fill(0));
    for (let i = 0; i < n; i++) {
        let maxVal = nums[i];
        let sum = nums[i];
        waste[i][i] = 0;
        for (let j = i + 1; j < n; j++) {
            maxVal = Math.max(maxVal, nums[j]);
            sum += nums[j];
            waste[i][j] = maxVal * (j - i + 1) - sum;
        }
    }
    
    // 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++) {
        // 不使用任何调整操作
        dp[i][0] = waste[0][i - 1];
        
        // 使用j次调整操作
        for (let j = 1; j <= Math.min(i - 1, k); j++) {
            for (let p = j; p < i; p++) {
                if (dp[p][j - 1] !== Infinity) {
                    dp[i][j] = Math.min(dp[i][j], dp[p][j - 1] + waste[p][i - 1]);
                }
            }
        }
    }
    
    let result = dp[n][0];
    for (let j = 1; j <= k; j++) {
        result = Math.min(result, dp[n][j]);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n³)预计算区间浪费 O(n²)，DP状态转移 O(n²k)，总体 O(n³)
空间复杂度O(n²)存储区间浪费空间的二维数组和DP数组