LeetCode 题解工作台
将数组分成最小总代价的子数组 II
给你一个下标从 0 开始长度为 n 的整数数组 nums 和两个 正 整数 k 和 dist 。 一个数组的 代价 是数组中的 第一个 元素。比方说， [1,2,3] 的代价为 1 ， [3,4,1] 的代价为 3 。 你需要将 nums 分割成 k 个 连续且互不相交 的 子数组 ，满足 第二 个…
4
题型
6
代码语言
3
相关题
当前训练重点
困难 · 数组·哈希·扫描
答案摘要
题目需要我们将数组 分割成 个连续且不相交的子数组，并且第二个子数组的第一个元素与第 个子数组的第一个元素的下标距离不超过 ，这等价于让我们从 下标为 的元素开始，找到一个窗口大小为 的子数组，求其中前 的最小元素之和。我们将 减 ，这样我们只需要求出 个最小元素之和，再加上 即可。 我们可以使用两个有序集合 和 分别维护大小为 $\textit{dist} + 1$ 的窗…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个下标从 0 开始长度为 n 的整数数组 nums 和两个 正 整数 k 和 dist 。
一个数组的 代价 是数组中的 第一个 元素。比方说，[1,2,3] 的代价为 1 ，[3,4,1] 的代价为 3 。
你需要将 nums 分割成 k 个 连续且互不相交 的子数组，满足 第二 个子数组与第 k 个子数组中第一个元素的下标距离 不超过 dist 。换句话说，如果你将 nums 分割成子数组 nums[0..(i1 - 1)], nums[i1..(i2 - 1)], ..., nums[ik-1..(n - 1)] ，那么它需要满足 ik-1 - i1 <= dist 。
请你返回这些子数组的 最小 总代价。
示例 1：
输入：nums = [1,3,2,6,4,2], k = 3, dist = 3 输出：5 解释：将数组分割成 3 个子数组的最优方案是：[1,3] ，[2,6,4] 和 [2] 。这是一个合法分割，因为 ik-1 - i1 等于 5 - 2 = 3 ，等于 dist 。总代价为 nums[0] + nums[2] + nums[5] ，也就是 1 + 2 + 2 = 5 。 5 是分割成 3 个子数组的最小总代价。
示例 2：
输入：nums = [10,1,2,2,2,1], k = 4, dist = 3 输出：15 解释：将数组分割成 4 个子数组的最优方案是：[10] ，[1] ，[2] 和 [2,2,1] 。这是一个合法分割，因为 ik-1 - i1 等于 3 - 1 = 2 ，小于 dist 。总代价为 nums[0] + nums[1] + nums[2] + nums[3] ，也就是 10 + 1 + 2 + 2 = 15 。 分割 [10] ，[1] ，[2,2,2] 和 [1] 不是一个合法分割，因为 ik-1 和 i1 的差为 5 - 1 = 4 ，大于 dist 。 15 是分割成 4 个子数组的最小总代价。
示例 3：
输入：nums = [10,8,18,9], k = 3, dist = 1 输出：36 解释：将数组分割成 3 个子数组的最优方案是：[10] ，[8] 和 [18,9] 。这是一个合法分割，因为 ik-1 - i1 等于 2 - 1 = 1 ，等于 dist 。总代价为 nums[0] + nums[1] + nums[2] ，也就是 10 + 8 + 18 = 36 。 分割 [10] ，[8,18] 和 [9] 不是一个合法分割，因为 ik-1 和 i1 的差为 3 - 1 = 2 ，大于 dist 。 36 是分割成 3 个子数组的最小总代价。
提示：
3 <= n <= 1051 <= nums[i] <= 1093 <= k <= nk - 2 <= dist <= n - 2
解题思路
方法一：有序集合
题目需要我们将数组 分割成 个连续且不相交的子数组，并且第二个子数组的第一个元素与第 个子数组的第一个元素的下标距离不超过 ，这等价于让我们从 下标为 的元素开始，找到一个窗口大小为 的子数组，求其中前 的最小元素之和。我们将 减 ，这样我们只需要求出 个最小元素之和，再加上 即可。
我们可以使用两个有序集合 和 分别维护大小为 的窗口元素，其中 维护最小的 个元素，而 维护窗口的剩余元素。我们维护一个变量 表示 与 中元素之和。初始时，我们将前 个元素之和累加到 中，并将下标为 的所有元素加入到 中。如果 的大小大于 ，我们循环将 中的最大元素移动到 中，直到 的大小等于 ，过程中更新 的值。
那么此时初始答案 。
接下来我们从 开始遍历 ，对于每一个元素 ，我们需要将 从 或 中移除，然后将 加入到 或 中。如果 小于 中的最大元素，我们将 加入到 中，否则加入到 中。如果此时 的大小小于 ，我们将 中的最小元素移动到 中，直到 的大小等于 。如果此时 的大小大于 ，我们将 中的最大元素移动到 中，直到 的大小等于 。过程中更新 的值，并更新 。
最终答案即为 。
时间复杂度 ，空间复杂度 。其中 为数组 的长度。
class Solution:
def minimumCost(self, nums: List[int], k: int, dist: int) -> int:
def l2r():
nonlocal s
x = l.pop()
s -= x
r.add(x)
def r2l():
nonlocal s
x = r.pop(0)
l.add(x)
s += x
k -= 1
s = sum(nums[: dist + 2])
l = SortedList(nums[1 : dist + 2])
r = SortedList()
while len(l) > k:
l2r()
ans = s
for i in range(dist + 2, len(nums)):
x = nums[i - dist - 1]
if x in l:
l.remove(x)
s -= x
else:
r.remove(x)
y = nums[i]
if y < l[-1]:
l.add(y)
s += y
else:
r.add(y)
while len(l) < k:
r2l()
while len(l) > k:
l2r()
ans = min(ans, s)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Ability to apply array scanning to partitioning problems.
- question_mark
Efficiency in using hash tables for dynamic lookups.
- question_mark
Understanding of sliding window techniques and their optimizations.
常见陷阱
外企场景- error
Incorrectly dividing the array without checking the distance constraint for each subarray.
- error
Inefficiently recalculating costs for overlapping subarrays.
- error
Failing to optimize the partition points dynamically, leading to higher computational complexity.
进阶变体
外企场景- arrow_right_alt
Adjust the problem by increasing the number of subarrays (k) or reducing the allowed distance (dist).
- arrow_right_alt
Allow some overlap between subarrays to explore different partitioning strategies.
- arrow_right_alt
Introduce additional constraints such as limiting the maximum or minimum value of elements within subarrays.