中间60%的k window之和
面经题，一个integer数组，返回k window的和，除去前后20%
另外的描述：有一个大小为n的数组，一个大小为k的窗口，1<k<=n, 窗口在数组上slide，每到一个位置去掉数值大小前x% 和后x%的数，然后求剩下的数的均值。对每一个窗口算一次，最后output出一个数组。求一个 nlogn的解法。。。
https://www.1point3acres.com/bbs/thread-490357-1-1.html
https://www.1point3acres.com/bbs/thread-477503-1-1.html
这可太segment tree了
面经题，一个integer数组，返回k window的和，除去前后20%
另外的描述：有一个大小为n的数组，一个大小为k的窗口，1<k<=n, 窗口在数组上slide，每到一个位置去掉数值大小前x% 和后x%的数，然后求剩下的数的均值。对每一个窗口算一次，最后output出一个数组。求一个 nlogn的解法。。。
https://www.1point3acres.com/bbs/thread-490357-1-1.html
https://www.1point3acres.com/bbs/thread-477503-1-1.html
这可太segment tree了
感觉可以用一个maxheap和一个minheap 大小分别为size = x% * k 来做
窗口从左走到右。
每次统计当前窗口内的数值。如果一个人sort当前窗口后，中间的100% - 2x%值求平均。
这样一个窗口会得到一个值。
如果我的这个理解是对的话，那么可以考虑先clone并全局sort一次得到每个数值的代号，用1个TreeSet来维护窗口来求-x% 和 x%。然后在树状数组里维护并求和。这样到好像的确是NLogN哦。
补充内容 (2019-2-19 01:47):
不用树状数组了，用三个TreeSet来维护0～x%, x～100-x% 和 100-x～100%。count是常数，用sum来记录中间的那个treeset的和。
请问大小x%是全局还是窗口的？
我猜大概是当前的，如果是全局的，O(n) 就可以。 这题用treemap做
这种sliding window的medium，average之类八成是multiset (BST/TreeSet)来做 我的想法就是每次删掉前面已经不在window的数，然后再减去前后x%? 但我想不出能够优化求和的更好方法了
这道题就是离扣四巴陵的变种，在java的条件下，用heap的时间复杂度是 O(n*k)，因为要把元素从heap里删掉, 如果不是堆顶元素的话，就需要O(k)复杂度。
