leetcode 3013. 将数组分成最小总代价的子数组 II【滑动窗口+multiset】

本文主要是介绍leetcode 3013. 将数组分成最小总代价的子数组 II【滑动窗口+multiset】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接：

​​​​​​3013. 将数组分成最小总代价的子数组 II

题目描述：

给你一个下标从 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
解释：将数组分割成 4 个子数组的最优方案是：[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 <= 1e5
• 1 <= nums[i] <= 1e9
• 3 <= k <= n
• k - 2 <= dist <= n - 2

解题思路：

题目要求将这个数组分为连续的k段，每段的贡献都是该段的第一个数，怎么分割能让k段的贡献之和最小，首先第一段的第一个数肯定是数组的第一个数，然后剩下的还有k-1段，要求第二段和最后一段的首元素位置之差小于等于dist，实际上就可以将原题目转换为在一个大小为dist+1的子数组中选择k-1个数使得这k-1个数的和最小，我们需要做的就是动态维护一个大小为dist+1的区间，然后从左往右滑动，实际上就是采用滑动窗口算法来依次遍历每一个区间，然后还需要做的就是对于每个区间怎么维护其中k-1个最小数的和，也就是窗口移动的同时需要维护窗口内k-1个最小的数的和，对于区间内k-1个最小的数我们可以采用multiset进行为维护，multiset是一个可以包含重复元素的有序集合，刚好这里我们需要维护的k-1个最小的数并且有重复元素，所以使用multiset维护是刚好可以的。

使用multiset具体维护过程如下

我们定义俩个multiset，分别为L和R，L用来维护大小为dist+1的区间内最小的k-1个数，R用来维护剩下的数。

首先将从第二个元素开始的dist+1个元素加入L，然后L就会将这dist+1个元素排序，然后我们就可以将最小的k-1个元素留在L中，剩下的移到R里面。

上面只是最开始的那个区间，然后每次左窗口向右移动一个位置，删除左窗口处的元素，如果左窗口处的元素位于L，那么就在L中删除，否则说明在R中，那么在R中删除，然后右窗口向右移动一个位置，判断这个新元素是否小于L中最大值，如果小于说明当前元素应该加入L，否则说明应该加入R,左右窗口每移动之后，还需要维护一下L的大小为k-1，然后更新答案。

时间复杂度：滑动窗口时间为O(n)，然后每次multiset都要find查找元素，那么查找为log的时间，multiset大小最大为dist，那么最终时间复杂度为O(nlog(dist)).

空间复杂度：multiset大小为dist，所以空间复杂度为O(dist).

cpp代码如下

class Solution {typedef long long LL;
public:long long minimumCost(vector<int>& nums, int k, int dist) {k--;   //首先将k--,那么下面就变为在dist+1个元素中选择k个最小的元素了int n=nums.size();LL sum=0;for(int i=0;i<dist+2;i++)sum+=nums[i];   //sum维护L中所有元素的和multiset<int>L(nums.begin()+1,nums.begin()+dist+2),R;auto LtoR=[&](){  //将L中的最大值移动R中int x=*L.rbegin();sum-=x;  //如果将L中的元素移出去了，那么sum要减去相应值L.erase(L.find(x));R.insert(x);};auto RtoL=[&](){  //将R中的最小值移动L中int x=*R.begin();sum+=x; //如果将某个值移入L，那么sum要加上相应值R.erase(R.find(x));L.insert(x);};//开始将dist+1个元素全部加入L了，但是L中只能留下最小的k个元素，剩下的移到R里面去while(L.size()>k){   LtoR();}LL ans=sum;for(int i=dist+2;i<n;i++){//移动左窗口int out=nums[i-dist-1];auto it=L.find(out);if(it!=L.end()){  //要删除的元素在L中L.erase(it);sum-=out;}else {   //要删除的元素在R中R.erase(R.find(out));}//移动右窗口int in=nums[i];if(in<*L.rbegin()){  //新加入的元素应该放在L中L.insert(in);sum+=in;}else {   //新加入的元素应该放在R中R.insert(in);}//每移动左右窗口一次,L大小可能为k-1,k,k+1,需要维护L的大小为kif(L.size()==k-1){RtoL();}else if(L.size()==k+1){LtoR();}//对于每个大小为dist+1的子数组更新答案ans=min(ans,sum);}return ans;}
};

这篇关于leetcode 3013. 将数组分成最小总代价的子数组 II【滑动窗口+multiset】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---