题目

你正在设计一个动态数组。给你一个下标从 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

解题思路分析

1、动态规划；时间复杂度O(n^3)，空间复杂度O(n^2)

func minSpaceWastedKResizing(nums []int, k int) int {
   n := len(nums)
   arr := make([][]int, n) // arr[i][j]表示nums[i:j]的最小浪费空间
   for i := 0; i < n; i++ {
      arr[i] = make([]int, n)
   }
   for i := 0; i < n; i++ {
      maxValue, sum := math.MinInt32, 0
      for j := i; j < n; j++ {
         if nums[j] > maxValue {
            maxValue = nums[j]
         }
         sum = sum + nums[j]
         arr[i][j] = maxValue*(j-i+1) - sum // 最大值*长度-总和
      }
   }
   dp := make([][]int, n) // dp[i][j]表示将nums[:i]分为j段的最小浪费空间
   for i := 0; i < n; i++ {
      dp[i] = make([]int, k+2)
      for j := 0; j < k+2; j++ {
         dp[i][j] = math.MaxInt32 / 10
      }
   }
   for i := 0; i < n; i++ {
      for j := 1; j <= k+1; j++ { // 调整k次，最少1段，最多k+1段
         for l := 0; l <= i; l++ {
            if l == 0 {
               dp[i][j] = arr[0][i]
            } else {
               dp[i][j] = min(dp[i][j], dp[l-1][j-1]+arr[l][i])
            }
         }
      }
   }
   return dp[n-1][k+1]
}

func min(a, b int) int {
   if a > b {
      return b
   }
   return a
}

总结

Medium题目，动态规划题目