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

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:27 2023-09-13 16:06:27 Updated    

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

方法一：动态规划 + 预处理

思路与算法

题目描述等价于：

给定数组 nums 以及整数 k，需要把数组完整地分成 k+1 段连续的子数组，每一段的权值是「这一段的最大值乘以这一段的长度再减去这一段的元素和」。需要最小化总权值。

我们可以使用动态规划解决本题。

记 f[i][j] 表示将 nums}[0..i] 分成 j 段的最小总权值。在进行状态转移时，我们可以枚举最后的一段，那么就有状态转移方程：

f[i][j] = \min_{0 \leq i_0 \leq i} { f[i_0-1][j-1] + g[i_0][i] }

其中 g[i_0][i] 表示「nums}[i_0..i] 这一段的最大值乘以这一段的长度再减去这一段的元素和」。在进行动态规划之前，我们可以使用二重循环预处理出所有的 g 值。

最终的答案即为 f[n-1][k+1]。

细节

在状态转移时我们需要枚举 i_0，而当 i_0 = 0 时，f[-1][j-1] 并不是一个合法的状态。

我们可以考虑 f[-1][..] 表示的意义：对于一段空的数组，我们希望将它分成若干段。由于每一段至少都要有一个元素，那么「空的数组」只能够分成 0 段，即 f[-1][0] = 0；而不能分成任意正整数段，即其余的 f[-1][..] = \infty（因为我们需要求出的是最小总权值，因此将不合法的状态标记为极大值）。

然而本题有一个很好的性质，即当 k_1 < k_2 时，分成 k_1 段的最小总权值一定不会小于分成 k_2 段的最小总权值，因此将所有的 f[-1][..] 都置为 0 也是不会影响最终答案的。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int minSpaceWastedKResizing(vector<int>& nums, int k) {
        int n = nums.size();

        // 预处理数组 g
        vector<vector<int>> g(n, vector<int>(n));
        for (int i = 0; i < n; ++i) {
            // 记录子数组的最大值
            int best = INT_MIN;
            // 记录子数组的和
            int total = 0;
            for (int j = i; j < n; ++j) {
                best = max(best, nums[j]);
                total += nums[j];
                g[i][j] = best * (j - i + 1) - total;
            }
        }
        
        vector<vector<int>> f(n, vector<int>(k + 2, INT_MAX / 2));
        for (int i = 0; i < n; ++i) {
            for (int j = 1; j <= k + 1; ++j) {
                for (int i0 = 0; i0 <= i; ++i0) {
                    f[i][j] = min(f[i][j], (i0 == 0 ? 0 : f[i0 - 1][j - 1]) + g[i0][i]);
                }
            }
        }

        return f[n - 1][k + 1];
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:
        n = len(nums)
        
        # 预处理数组 g
        g = [[0] * n for _ in range(n)]
        for i in range(n):
            # 记录子数组的最大值
            best = float("-inf")
            # 记录子数组的和
            total = 0
            for j in range(i, n):
                best = max(best, nums[j])
                total += nums[j]
                g[i][j] = best * (j - i + 1) - total
        
        f = [[float("inf")] * (k + 2) for _ in range(n)]
        for i in range(n):
            for j in range(1, k + 2):
                for i0 in range(i + 1):
                    f[i][j] = min(f[i][j], (0 if i0 == 0 else f[i0 - 1][j - 1]) + g[i0][i])

        return f[n - 1][k + 1]

复杂度分析

  • 时间复杂度：O(n^2k)，其中 n 是数组 nums 的长度。状态的数量为 O(nk)，每个状态需要 O(n) 的时间枚举 i_0 进行转移。

  • 空间复杂度：O(n(n+k))。我们需要 O(n^2) 的空间存储数组 g，O(nk) 的空间存储所有的状态。

 Comments
On this page
1959-K 次调整数组大小浪费的最小总空间