将数组分成最小总代价的子数组 II
给你一个下标从 0 开始长度为 n 的整数数组 nums 和两个 正 整数 k 和 dist 。
一个数组的 代价 是数组中的 第一个 元素。比方说，[1,2,3] 的代价为 1 ，[3,4,1] 的代价为 3 。
你需要将 nums 分割成 k 个 连续且互不相交 的子数组，满足 第二 个子数组与第 k 个子数组中第一个元素的下标距离 不超过 dist 。换句话说，如果你将 nums 分割成子数组 $nums[0..(i_1 - 1)], nums[i_1..(i_2 - 1)], …, nums[i_{k-1}..(n - 1)] ，$
那么它需要满足
$i_{k-1} - i_1 <= dist$
请你返回这些子数组的 最小 总代价。
提示：
- 3 <= n <= 105
- 1 <= nums[i] <= 109
- 3 <= k <= n
- k - 2 <= dist <= n - 2
思路
从将 nums 分割成 k 个 连续且互不相交 的子数组得到
$k-2<=i_{k-1} - i_1 <= dist$
因为0号在划分的第一个子数组的首位，nums[0]必然累加在最后的结果中。
原问题就转化为了对大小为n-1的数组进行大小为dist+1的滑动窗口查找，查找窗口内前k-1小的元素的最小和。
两个有序集合维护前 k-1 小
- 初始化两个有序集合 L 和 R。注意：为方便计算，把 k 减一。
- 把 nums[1] 到 nums[dist+1] 加到 L 中。
- 保留 L 最小的 k 个数，把其余数丢到 R 中。
- 从 i=dist+2 开始滑窗。
- 先把 out=nums[i−dist−1] 移出窗口：如果 out 在 L 中，就从 L 中移除，否则从 R 中移除。
- 然后把 in=nums[i] 移入窗口：如果 in 小于 L 中的最大元素，则加入 L，否则加入 R。
- 上面两步做完后，如果 L 中的元素个数小于 k（等于 k−1），则从 R 中取一个最小元素加入 L；反之，如果 L 中的元素个数大于 k（等于 k+1），则从 L 中取一个最大元素加入 R。
- 上述过程维护 L 中元素之和 sumL，取 sumL 的最小值，即为答案。
参考
