在需要动态维护滑动窗口内的统计量(如前 K 小值之和或中位数)时,可以使用两个有序集合来实现高效更新。
基本思路:
先确定窗口长度以及在窗口中要维护的元素数量,然后用两个集合 big/small 来区分管理:big 存储当前窗口中符合要求的 K 个元素;small 存储窗口中的其他元素;根据题意决定使用 set 或 multiset,前者不允许重复,后者可以处理重复值。
rebalance
在维护过程中,关键是 rebalance 操作。它负责保持两个集合之间的数量与顺序约束,当 big 的元素数少于目标数量时,就从 small 中取出最高优先级元素转移到 big;若 small 中存在比 big 中优先级更高的元素,则交换两者,使得 big 始终保存窗口中优先级最高的那部分。
auto rebalance=[&](){// 数量少则补while(big.size()<k-1 && !small.empty()){auto it=small.begin();sum+=*it;big.insert(*it);small.erase(it);}// 优先级低则换while(!big.empty() && !small.empty()){auto r = prev(big.end()),l=small.begin();int R=*r, L=*l;if(L<R){sum+=L-R;big.erase(r);big.insert(L);small.erase(l);small.insert(R);}else break;}
};
add/remove
更新时,add 和 remove 分别对应窗口的右移操作。add 用于加入新进入窗口的元素,先插入到 small,再执行一次 rebalance;remove 用于移除滑出窗口的元素,优先从 big 中删除,若不存在再在 small 中删除,之后同样调用 rebalance;根据题意/元素类型看是否添加其他逻辑。
