Question

1959. K 次调整数组大小浪费的最小总空间

English Version

题目描述

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

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

在调整数组大小不超过 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] <= 106
• 0 <= k <= nums.length - 1

解法

方法一：动态规划

class Solution:
  def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:
    k += 1
    n = len(nums)
    g = [[0] * n for _ in range(n)]
    for i in range(n):
      s = mx = 0
      for j in range(i, n):
        s += nums[j]
        mx = max(mx, nums[j])
        g[i][j] = mx * (j - i + 1) - s
    f = [[inf] * (k + 1) for _ in range(n + 1)]
    f[0][0] = 0
    for i in range(1, n + 1):
      for j in range(1, k + 1):
        for h in range(i):
          f[i][j] = min(f[i][j], f[h][j - 1] + g[h][i - 1])
    return f[-1][-1]

class Solution {
  public int minSpaceWastedKResizing(int[] nums, int k) {
    ++k;
    int n = nums.length;
    int[][] g = new int[n][n];
    for (int i = 0; i < n; ++i) {
      int s = 0, mx = 0;
      for (int j = i; j < n; ++j) {
        s += nums[j];
        mx = Math.max(mx, nums[j]);
        g[i][j] = mx * (j - i + 1) - s;
      }
    }
    int[][] f = new int[n + 1][k + 1];
    int inf = 0x3f3f3f3f;
    for (int i = 0; i < f.length; ++i) {
      Arrays.fill(f[i], inf);
    }
    f[0][0] = 0;
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= k; ++j) {
        for (int h = 0; h < i; ++h) {
          f[i][j] = Math.min(f[i][j], f[h][j - 1] + g[h][i - 1]);
        }
      }
    }
    return f[n][k];
  }
}

class Solution {
public:
  int minSpaceWastedKResizing(vector<int>& nums, int k) {
    ++k;
    int n = nums.size();
    vector<vector<int>> g(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
      int s = 0, mx = 0;
      for (int j = i; j < n; ++j) {
        mx = max(mx, nums[j]);
        s += nums[j];
        g[i][j] = mx * (j - i + 1) - s;
      }
    }
    int inf = 0x3f3f3f3f;
    vector<vector<int>> f(n + 1, vector<int>(k + 1, inf));
    f[0][0] = 0;
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= k; ++j) {
        for (int h = 0; h < i; ++h) {
          f[i][j] = min(f[i][j], f[h][j - 1] + g[h][i - 1]);
        }
      }
    }
    return f[n][k];
  }
};

func minSpaceWastedKResizing(nums []int, k int) int {
  k++
  n := len(nums)
  g := make([][]int, n)
  for i := range g {
    g[i] = make([]int, n)
  }
  for i := 0; i < n; i++ {
    s, mx := 0, 0
    for j := i; j < n; j++ {
      s += nums[j]
      mx = max(mx, nums[j])
      g[i][j] = mx*(j-i+1) - s
    }
  }
  f := make([][]int, n+1)
  inf := 0x3f3f3f3f
  for i := range f {
    f[i] = make([]int, k+1)
    for j := range f[i] {
      f[i][j] = inf
    }
  }
  f[0][0] = 0
  for i := 1; i <= n; i++ {
    for j := 1; j <= k; j++ {
      for h := 0; h < i; h++ {
        f[i][j] = min(f[i][j], f[h][j-1]+g[h][i-1])
      }
    }
  }
  return f[n][k]
}