1959. K 次调整数组大小浪费的最小总空间
题目描述
你正在设计一个动态数组。给你一个下标从 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 <= 2001 <= nums[i] <= 1060 <= k <= nums.length - 1
解法
方法一：动态规划
题目等价于我们将数组 $\textit{nums}$ 分成 $k + 1$ 段，那么每一段的浪费空间为该段的最大值乘以该段的长度减去该段的元素之和。我们累加每一段的浪费空间，即可得到总浪费空间。我们将 $k$ 加 $1$，那么就相当于将数组分成 $k$ 段。
因此，我们定义数组 $\textit{g}[i][j]$ 表示 $\textit{nums}[i..j]$ 的最大值乘以 $\textit{nums}[i..j]$ 的长度减去 $\textit{nums}[i..j]$ 的元素之和。我们在 $[0, n)$ 的范围内枚举 $i$，在 $[i, n)$ 的范围内枚举 $j$，用一个变量 $s$ 维护 $\textit{nums}[i..j]$ 的元素之和，用一个变量 $\textit{mx}$ 维护 $\textit{nums}[i..j]$ 的最大值，那么我们可以得到：
$$ \textit{g}[i][j] = \textit{mx} \times (j - i + 1) - s $$
接下来，我们定义 $\textit{f}[i][j]$ 表示前 $i$ 个元素分成 $j$ 段的最小浪费空间。我们初始化 $\textit{f}[0][0] = 0$，其余位置初始化为无穷大。我们在 $[1, n]$ 的范围内枚举 $i$，在 $[1, k]$ 的范围内枚举 $j$，然后我们枚举前 $j - 1$ 段的最后一个元素 $h$，那么有：
$$
\textit{f}[i][j] = \min(\textit{f}[i][j],
\textit{f}[h][j - 1] + \textit{g}[h][i - 1])
$$
最终答案为 $\textit{f}[n][k]$。
时间复杂度 $O(n^2 \times k)$，空间复杂度 $O(n \times (n + k))$。其中 $n$ 为数组 $\textit{nums}$ 的长度。
Python3
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]
Java
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];
}
}
C++
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];
}
};
Go
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]
}
TypeScript
function minSpaceWastedKResizing(nums: number[], k: number): number {
k += 1;
const n = nums.length;
const g: number[][] = Array.from({ length: n }, () => Array(n).fill(0));
for (let i = 0; i < n; i++) {
let s = 0,
mx = 0;
for (let j = i; j < n; j++) {
s += nums[j];
mx = Math.max(mx, nums[j]);
g[i][j] = mx * (j - i + 1) - s;
}
}
const inf = Number.POSITIVE_INFINITY;
const f: number[][] = Array.from({ length: n + 1 }, () => Array(k + 1).fill(inf));
f[0][0] = 0;
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= k; j++) {
for (let 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];
}
Rust
impl Solution {
pub fn min_space_wasted_k_resizing(nums: Vec<i32>, k: i32) -> i32 {
let mut k = k + 1;
let n = nums.len();
let mut g = vec![vec![0; n]; n];
for i in 0..n {
let (mut s, mut mx) = (0, 0);
for j in i..n {
s += nums[j];
mx = mx.max(nums[j]);
g[i][j] = mx * (j as i32 - i as i32 + 1) - s;
}
}
let inf = 0x3f3f3f3f;
let mut f = vec![vec![inf; (k + 1) as usize]; n + 1];
f[0][0] = 0;
for i in 1..=n {
for j in 1..=k as usize {
for h in 0..i {
f[i][j] = f[i][j].min(f[h][j - 1] + g[h][i - 1]);
}
}
}
f[n][k as usize]
}
}