LeetCode 题解工作台
K 次调整数组大小浪费的最小总空间
你正在设计一个动态数组。给你一个下标从 0 开始的整数数组 nums ，其中 nums[i] 是 i 时刻数组中的元素数目。除此以外，你还有一个整数 k ，表示你可以 调整 数组大小的 最多 次数（每次都可以调整成 任意 大小）。 t 时刻数组的大小 size t 必须大于等于 nums[t] ，因…
2
题型
6
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
题目等价于我们将数组 分成 $k + 1$ 段，那么每一段的浪费空间为该段的最大值乘以该段的长度减去该段的元素之和。我们累加每一段的浪费空间，即可得到总浪费空间。我们将 加 ，那么就相当于将数组分成 段。 因此，我们定义数组 表示 的最大值乘以 的长度减去 的元素之和。我们在 $[0, n)$ 的范围内枚举 ，在 $[i, n)$ 的范围内枚举 ，用一个变量 维护 的元素之和，用…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
你正在设计一个动态数组。给你一个下标从 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
解题思路
方法一：动态规划
题目等价于我们将数组 分成 段，那么每一段的浪费空间为该段的最大值乘以该段的长度减去该段的元素之和。我们累加每一段的浪费空间，即可得到总浪费空间。我们将 加 ，那么就相当于将数组分成 段。
因此，我们定义数组 表示 的最大值乘以 的长度减去 的元素之和。我们在 的范围内枚举 ，在 的范围内枚举 ，用一个变量 维护 的元素之和，用一个变量 维护 的最大值，那么我们可以得到：
接下来，我们定义 表示前 个元素分成 段的最小浪费空间。我们初始化 ，其余位置初始化为无穷大。我们在 的范围内枚举 ，在 的范围内枚举 ，然后我们枚举前 段的最后一个元素 ，那么有：
最终答案为 。
时间复杂度 ，空间复杂度 。其中 为数组 的长度。
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]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Assess the candidate's understanding of dynamic programming and its application in array resizing problems.
- question_mark
Evaluate the candidate's ability to break down the problem into subproblems and use state transitions to minimize wasted space.
- question_mark
Check if the candidate can optimize their solution by precomputing waste and leveraging past results effectively.
常见陷阱
外企场景- error
Forgetting to account for the minimal wasted space when no resizes are allowed (k = 0).
- error
Incorrectly handling the dynamic programming state transitions, leading to excessive or suboptimal resizing operations.
- error
Neglecting to precompute the total waste for ranges, resulting in slower solutions that don't take advantage of overlapping subproblems.
进阶变体
外企场景- arrow_right_alt
Modify the problem to allow resizing only once and observe how the solution changes.
- arrow_right_alt
Change the array size and constraints to test the scalability of the solution for larger inputs.
- arrow_right_alt
Introduce additional constraints such as limiting the maximum array size to test how the solution adapts.