这里对每个大小堆维护一个哈希，来标记已删除的元素，并同时维护一个容量值，标记实际元素个数，来保证大小堆平衡。
class Solution { public: priority_queue<int,vector<int>,greater<int> > qmn; // 小根堆，生序 priority_queue<int,vector<int>,less<int> > qmx; // 大根堆，降序 map<int,int> mpmn,mpmx; vector<double> ans; int lmn,lmx; vector<double> medianSlidingWindow(vector<int>& nums, int k) { if(nums.size() == 0) return ans; lmn = lmx = 0; qmx.push(nums[0]); lmx++; for(int i=1;i<k;i++){ if(nums[i] <= qmx.top()){ qmx.push(nums[i]); lmx ++; }else{ qmn.push(nums[i]); lmn ++; } build(); } ans.push_back(find_mid()); for(int i=k;i<nums.size();i++){ if(nums[i] <= qmx.top()){ qmx.push(nums[i]); lmx++; }else{ qmn.push(nums[i]); lmn++; } if(nums[i-k]<=qmx.top()){ lmx--; mpmx[nums[i-k]] ++; } else{ mpmn[nums[i-k]] ++; lmn --; } build(); ans.push_back(find_mid()); } return ans; } double find_mid(){ while((qmx.size()>0&&mpmx[qmx.top()])>0|| (qmn.size()>0&&mpmn[qmn.top()]>0)){ if(qmx.size()>0&&mpmx[qmx.top()]>0){ mpmx[qmx.top()] --; qmx.pop(); } if(qmn.size()>0&&mpmn[qmn.top()]>0){ mpmn[qmn.top()] --; qmn.pop(); } build(); } if(lmx > lmn) return qmx.top(); return ((long long)qmx.top() + qmn.top())/2.0; } void build(){ while(lmn > lmx){ int t = qmn.top(); qmn.pop(); if(mpmn[t] > 0){ mpmn[t] --; }else{ qmx.push(t); lmx ++; lmn --; } } while(lmn+1 < lmx){ int t = qmx.top(); qmx.pop(); if(mpmx[t] > 0){ mpmx[t] --; }else{ qmn.push(t); lmn ++; lmx --; } } } };