今日学习记录
3321. 计算子数组的 x-sum II
关键词：滑动窗口 对顶堆
问题分析
给定一个窗口的大小,要求给定数组中满足窗口大小的连续子数组的 x-sum,仅计算子数组中出现次数前 x 大的数,次数相同就是大小优先,然后求总和,返回一个 ans,包含每个窗口的 x-sum 值
核心思路
滑动窗口
首先给定了长度,那么就是典型的定长滑窗,先套一层定长滑窗的模板
对顶堆(介绍)
主要是滑窗的中间答案过程,我们要获得每次的前两个次数最多的数,维护前 x 大的数就是经典的对顶堆问题,我们使用两个优先队列,对于第 x 大的数来说,他左边的数都比他小,所以左堆为最大堆,第 x 大的数为堆顶,他右边的数都比他大,但是他为堆顶,所以右堆为最小堆,我们要保证右堆的长度不能超过 x,这样右堆装的就是最大的 x 个数,对于每次维护,都与堆顶比较,大于堆顶就 pop 掉堆顶(注意
),然后入右堆,小于则入左堆(注意),这样我就可以每次取到前 x 大的数了,两个堆顶相对着实现的就是对顶堆核心思想转换
我们要解决的问题是维护前 k 大的数,双堆解法是针对最经典的维护中位数问题,在此题目中要进行频繁的修改标记(使用懒删除)实现是很难的,我们不再局限于双堆做法,而是把目标转到维护前k大的数这个问题上,我们为什么选择大小根堆,是因为他会自动排序,我们不可能在每次加入数组后再进行排序,这样时间复杂度极高,如果仅仅如此,我们还可以使用另一种数据结构multiset(平衡二叉树)来实现,可是再往回看,为什么要选择大小根堆,而不选择一个优先队列,是因为堆不支持随机访问,所以我想要获取中间数很麻烦,而堆只能获取堆顶,所以使用两个堆,但是 multiset 支持随机访问,但是这个访问时间是 O(n),在大多数题目中其实 multiset 可以替代双堆做法的,但是我们要讨论的是最优解法,所以这样可以看出双堆的设计原理,所以回到问题核心上,就是要维护两个有序集合而已
再回到本题,我们要频繁的删除插入,以上两种数据结构似乎都不行,我们可以根据核心理念维护两个有序集合设计本题做法,我们使用红黑树实现的 set,两个 set,一个把第 k 大的数当 end,一个当 begin(),这样也可以直接访问,而且 set 集合易于删除
后续依旧用堆来介绍,但实现还是set
实现细节
我们要计算自然是把值和次数同时放到堆中去比较,因为比的不止是次数,还要比较值,我们对于实际操作关键点在于插入删除,要插入 p 的时候,先把堆中的 p 删除,再把 p 加一放入到堆中,p 出堆的时候要先删除 p,再把 p 数量减一再放入到堆中,三个频繁的操作,整合一下
- 平衡堆
- 删除
- 插入
**最终代码：
class Solution {
public:
vector<long long> findXSum(vector<int>& nums, int k, int x) {
set<pair<int,int>> left,right;
unordered_map<int,int> mp;
long long sum = 0;
vector<long long> ans(nums.size() - k + 1);
auto del = [&](int num){
if(mp[num]==0) return;
pair<int,int> p = {mp[num],num};
auto it = left.find(p);
if(it!=left.end()){
sum -= 1LL*p.first*p.second;
left.erase(it);
}
else right.erase(p);
};
auto add = [&](int num){
if(mp[num]==0) return;
pair<int,int> p = {mp[num],num};
if(!left.empty()&&p>*left.begin()){
sum += 1LL*p.first*p.second;
left.insert(p);
}
else right.insert(p);
};
auto l2r = [&]() {
auto p = *left.begin();
sum -= (long long) p.first * p.second;
left.erase(p);
right.insert(p);
};
auto r2l = [&]() {
auto p = *right.rbegin();
sum += (long long) p.first * p.second;
right.erase(p);
left.insert(p);
};
for(int r = 0;r<nums.size();r++){
int in = nums[r];
del(in);
mp[in]++;
add(in);
int l = r-k+1;
if(l<0) continue;
//平衡堆
while(!right.empty()&&left.size()<x){
r2l();
}
while(left.size()>x){
l2r();
}
ans[l] = sum;
//删除
int out = nums[l];
del(out);
mp[out]--;
add(out);
}
return ans;
}
};学到的点：
- 对顶堆理念使用