我们来实现 LeetCode 1825 的MKAverage类中的addElement方法。题目要求维护一个数据流计算最后M个元素中去掉最小的K个和最大的K个后剩余元素的平均值即 MK 平均值。核心思路由于M和元素值范围1 ≤ num ≤ 10^5都不大可以使用两个 Fenwick 树树状数组高效地维护一个树状数组cnt记录每个值的出现次数一个树状数组sum记录每个值的元素和同时用一个队列维护元素添加的顺序以便在窗口超过M时移除最早的元素。操作流程addElement(num)将num加入队列在cnt和sum的num位置上增加 1 和num如果队列长度超过M则取出队首元素old将其从树状数组中减去 1次数和old和calculateMKAverage()若当前元素总数 M返回-1利用树状数组的第 K 小查询通过二分查找前缀和得到第K小的值minK和 第M-K1小的值即第M-K大的位置但由于我们只需要去掉最小的 K 个和最大的 K 个实际上可以用前 K 个元素的和 前缀和到第 K 小的位置需注意可能多个相同值的处理后 K 个元素的和 总和 - 前缀和到第M-K小的位置中间部分的和 总和 - 前 K 小和 - 后 K 大和平均值 中间和 / (M - 2*K)关键点处理相同值的边界由于存在相同值我们不能简单取第 K 个元素的值然后乘以 K。需要精确计算前 K 个元素的和即使第 K 个值重复出现也要只取其中的一部分。例如值域中第 K 小的数x出现了c次而前缀到x-1有cntPre个元素那么前 K 个元素包含全部的x-1及更小的值以及(K - cntPre)个x。前 K 小和 sumPre (K - cntPre) * x。后 K 大同理设第M-K小的数为y前缀到y有total个元素可能超过M-K则后 K 大包含所有大于y的值以及一部分y。实现代码classMKAverage{privateintM,K;privateQueueIntegerqueue;privateFenwickTreecnt;// 频数树状数组privateFenwickTreesum;// 和树状数组privateintmaxVal100000;// 题目给出的最大值publicMKAverage(intm,intk){Mm;Kk;queuenewLinkedList();cntnewFenwickTree(maxVal2);sumnewFenwickTree(maxVal2);}publicvoidaddElement(intnum){// 1. 加入新元素queue.offer(num);cnt.add(num,1);sum.add(num,num);// 2. 如果超出窗口大小移除最早元素if(queue.size()M){intoldqueue.poll();cnt.add(old,-1);sum.add(old,-old);}}publicintcalculateMKAverage(){if(queue.size()M)return-1;// 总和 所有元素的和longtotalSumsum.prefixSum(maxVal);// 前 K 个元素的和longsmallSumgetKthSum(K);// 后 K 个元素的和 总和 - 前 (M-K) 个元素的和longlargeSumtotalSum-getKthSum(M-K);longmidSumtotalSum-smallSum-largeSum;intmidCountM-2*K;return(int)(midSum/midCount);}// 计算最小的 k 个元素的和privatelonggetKthSum(intk){// 找到第 k 小的元素值 valintvalcnt.findKth(k);// 小于 val 的元素个数intcntLesscnt.prefixSum(val-1);// 小于 val 的元素和longsumLesssum.prefixSum(val-1);// 还需要取多少个 valintneedk-cntLess;returnsumLess(long)need*val;}// 树状数组实现支持单点更新、前缀和查询、第 K 小查询classFenwickTree{intn;int[]tree;FenwickTree(intn){this.nn;treenewint[n];}voidadd(intidx,intdelta){while(idxn){tree[idx]delta;idxidx-idx;}}intprefixSum(intidx){intres0;while(idx0){restree[idx];idx-idx-idx;}returnres;}// 查找最小的 index 使得前缀和 k第 k 小intfindKth(intk){intidx0;intbitMaskInteger.highestOneBit(n);while(bitMask!0){inttIdxidxbitMask;if(tIdxntree[tIdx]k){idxtIdx;k-tree[tIdx];}bitMask1;}returnidx1;}}}复杂度分析addElementO(log V)其中 V 是值域范围1e5calculateMKAverageO(log V)主要开销是树状数组的二分查找和前缀和查询空间复杂度O(M V)注意事项树状数组版本的第 K 小查询要求数组中元素频数非负且 k 有效不会超过总频数由于需要同时维护频数树和和树每次更新保持同步移除元素时通过队列保证 FIFO 顺序此解法能够高效处理大数据流满足题目要求。