LeetCode 3013.将数组分成最小总代价的子数组 II：两个堆维护k-1小 + 滑动窗口-编程实验室

【LetMeFly】3013.将数组分成最小总代价的子数组 II：两个堆维护k-1小 + 滑动窗口

力扣题目链接：https://leetcode.cn/problems/divide-an-array-into-subarrays-with-minimum-cost-ii/

给你一个下标从0开始长度为n的整数数组nums和两个正整数k和dist。

一个数组的代价是数组中的第一个元素。比方说，[1,2,3]的代价为1，[3,4,1]的代价为3。

你需要将nums分割成k个连续且互不相交的子数组，满足第二个子数组与第k个子数组中第一个元素的下标距离不超过dist。换句话说，如果你将nums分割成子数组nums[0..(i₁- 1)], nums[i₁..(i₂- 1)], ..., nums[i_k-1..(n - 1)]，那么它需要满足i_k-1- i₁<= dist。

请你返回这些子数组的最小总代价。

示例 1：

输入：nums = [1,3,2,6,4,2], k = 3, dist = 3输出：5解释：将数组分割成 3 个子数组的最优方案是：[1,3] ，[2,6,4] 和 [2] 。这是一个合法分割，因为 i_k-1- i₁等于 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] 。这是一个合法分割，因为 i_k-1- i₁等于 3 - 1 = 2 ，小于 dist 。总代价为 nums[0] + nums[1] + nums[2] + nums[3] ，也就是 10 + 1 + 2 + 2 = 15 。 分割 [10] ，[1] ，[2,2,2] 和 [1] 不是一个合法分割，因为 i_k-1和 i₁的差为 5 - 1 = 4 ，大于 dist 。 15 是分割成 4 个子数组的最小总代价。

示例 3：

输入：nums = [10,8,18,9], k = 3, dist = 1输出：36解释：将数组分割成 4 个子数组的最优方案是：[10] ，[8] 和 [18,9] 。这是一个合法分割，因为 i_k-1- i₁等于 2 - 1 = 1 ，等于 dist 。总代价为 nums[0] + nums[1] + nums[2] ，也就是 10 + 8 + 18 = 36 。 分割 [10] ，[8,18] 和 [9] 不是一个合法分割，因为 i_k-1和 i₁的差为 3 - 1 = 2 ，大于 dist 。 36 是分割成 3 个子数组的最小总代价。

提示：

3 <= n <= 10⁵
1 <= nums[i] <= 10⁹
3 <= k <= n
k - 2 <= dist <= n - 2

解题方法：有序集合 + 滑动窗口

n u m s numsnums第一个元素必选，剩下k − 1 k-1k−1个元素的起始位置间隔必须≤ d i s t \leq dist≤dist。使用一个大小为d i s t + 1 dist+1dist+1的滑动窗口，每次求这个窗口中k − 1 k-1k−1小元素的和。

问题变成了滑动窗口向右滑动过程中，窗口中不断新增一个元素、移除一个元素的状态下如何保持计算k − 1 k-1k−1小的元素有哪些：

我们可以使用两个有序集合，一个叫s t a g e stagestage代表(正在舞台上的)k − 1 k-1k−1小元素，一个叫c a n d i d a t e candidatecandidate代表在窗口中但(暂)未被选中的元素。
窗口右移过程中，假设要新加入窗口的元素是i n inin，移除窗口的元素是o u t outout，
对于o u t outout有：
如果o u t outout在c a n d i d a t e candidatecandidate候选集合中，那么o u t outout永无上台之日，直接移出候选
如果o u t outout在s t a g e stagestage选中集合中，那么o u t outout是时候退役了，移出s t a g e stagestage集合，并更新集合中元素之和
对于i n inin有：
如果i n inin比s t a g e stagestage中最大元素小，说明更优秀的人来了，移出s t a g e stagestage集合中最大的那个，将i n inin加入s t a g e stagestage集合，并更新s t a g e stagestage集合中元素之和
否则，将i n inin加入候选
之后进行s t a g e stagestage集合大小的调整：
如果s t a g e stagestage集合小于k − 1 k-1k−1，说明有人退役暂无人顶上，从c a n d i d a t e candidatecandidate中选最小的那个顶上(移出c a n d i d a t e candidatecandidate并加入s t a g e stagestage)，并更新s t a g e stagestage集合中元素之和
如果s t a g e stagestage集合大于k + 1 k+1k+1，说明有更优秀的人来了，要把s t a g e stagestage中最大的那个移出并加入到c a n d i d a t e candidatecandidate，并更新s t a g e stagestage集合中元素之和

整个滑动窗口移动的过程中，所有s t a g e stagestage元素和中最小的那个即为答案。

为了方便计算，我们开局直接把k kk减一。

时间复杂度O ( n log ⁡ d i s t ) O(n\log dist)O(nlogdist)
空间复杂度O ( d i s t ) O(dist)O(dist)

AC代码

C++

/* * @LastEditTime: 2026-02-03 22:11:11 */typedeflonglongll;classSolution{public:llminimumCost(vector<int>&nums,intk,intdist){k--;multiset<ll>stage(nums.begin()+1,nums.begin()+dist+2),candidate;ll ans=accumulate(nums.begin(),nums.begin()+dist+2,0ll);while(stage.size()>k){intretiree=*stage.rbegin();stage.erase(prev(stage.end()));ans-=retiree;candidate.insert(retiree);}ll nowAns=ans;for(intend=dist+2;end<nums.size();end++){intin=nums[end],out=nums[end-dist-1];// outmultiset<ll>::iterator it=candidate.find(out);if(it!=candidate.end()){candidate.erase(it);}else{stage.erase(stage.find(out));nowAns-=out;}// inif(in<*stage.rbegin()){stage.insert(in);nowAns+=in;}else{candidate.insert(in);}// resizeif(stage.size()==k-1){intnewActor=*candidate.begin();candidate.erase(candidate.begin());stage.insert(newActor);nowAns+=newActor;}elseif(stage.size()==k+1){intretiree=*stage.rbegin();stage.erase(prev(stage.end()));nowAns-=retiree;candidate.insert(retiree);}ans=min(ans,nowAns);}returnans;}};#ifdefined(_WIN32)||defined(__APPLE__)/* [1,3,2,6,4,2] 3 3 5 */intmain(){string s;inta,b;while(cin>>s>>a>>b){Solution sol;vector<int>v=stringToVector(s);cout<<sol.minimumCost(v,a,b)<<endl;}return0;}#endif