leetcode 480. 滑动窗口中位数(用两个个数一样或差1的大小根堆实现)

题目

比如 123456789 k=4;
刚开始q1(大根堆里面是) 21 ，q2是 34 则通过q1的栈顶或者和q2的栈顶得到中位数。
删除元素怎么办呢？比如q1删除了元素4，则++mp[4]，标记一下，那q1减了一个元素，0<=q1-q2<=1就不满足啦，所以应该标记一下这个数。
同样插入元素x的时候，x<=q1.top()，插入q1,否则插入q2。也会导致不平衡，平衡是为了保证求中位数的策略是对的。
删除和插入完之后应该通过这个标记的数，决定q1给q2多少元素，或者q2给q1多少。
最后处理一下q1,q2,若mp[栈顶]有值，说明无效，则top();
比如123456789这个序列会导致q1里面的无效的一直不会是栈顶，堆就变大。
复杂度最优：nlogk 最坏:nlogn 所以复杂度算是nlogn；
为什么不权值线段树 nlogk
为什么不手写堆，hash一下它的位置这样就可以完成堆的删除了，不是虚假删除了保证了复杂度，相同元素多个位置要存起来，map<int,vector>男朋友说可以multimap…忘了。

class Solution {
public:
    vector<double> medianSlidingWindow(vector<int>& nums, int k){
        vector<double>ans;
        unordered_map<int,int>mp;
        priority_queue<int>q1;
        priority_queue<int,vector<int>,greater<int>>q2;
        int i=0;
        for(;i<k;++i) q1.push(nums[i]);
        for(int j=0;j<k/2;++j) q2.push(q1.top()),q1.pop();
        while(1){
            ans.push_back((k&1)?q1.top():(q1.top()*1.0+q2.top())/2);//q1.top()+q2.top()可能会爆int
            if(i>=nums.size()) break;
            int x=nums[i-k],y=nums[i++],flag=0;
            ++mp[x],flag=(x<=q1.top())?-1:1;//删除x元素 flag标记当前平衡的基础上 q1的有效个数比q2有效多了几个
            if(y<=q1.top()) q1.push(y),++flag;//把y放入q1
            else q2.push(y),--flag;//把y放入q1
            //保证0<=q1有效个数-q2有效个数<=1
            if(flag<0) q1.push(q2.top()),q2.pop();
            if(flag>0) q2.push(q1.top()),q1.pop();
            //删除无效的数
            while(mp[q1.top()]) --mp[q1.top()],q1.pop();
            while(!q2.empty()&&mp[q2.top()]) --mp[q2.top()],q2.pop();
        }
        return ans;
    }
};