第一次写题
    这道题最大的难点在于想清楚插入到哪一个堆，又从哪一个堆删除数据。我们一开始用balance = 0表示数量平衡的状态，最大堆比最小堆多，balance就+1，比最小堆少balance就-1。插入最大堆相当于最大堆增多是balance +1，删除最大堆的元素相当于是balance -1。插入到最小堆是balance - 1，删除最大堆的元素是balance +1。
    从最大堆（max_heap）删除数据会让balance -1，插入最小堆（min_heap）会让balance -1，因为前一轮max_heap的top和min_heap的top都是可以用的，现在从max_heap删除，插入到min_heap，能确定的是min_heap的top是可以用的！并且max_heap现在是少了东西，需要从min_heap拿。因此直接拿min_heap的top就可以。
    还有一个问题是，为什么balance = -2只要转移一个数据？不是转移两个数据？首先，要想清楚的是，如果a是奇数，然后分成两堆a1、 a2，必然是a1、a2中一个奇数一个偶数。因此我们从一堆中删除一个并不影响它的平衡（虽然说我们是希望让最大堆的比最小堆的多一个数字，但是最小堆比最大堆多一个数字也不是不平衡）。因此删掉了一个还是平衡的，那么再插入一个呢？这个时候如果插入的是对面的堆，那么balance = -2。一边少了一个，另外一边多了一个，本来少了的就少了也是平衡。但是现在对面的多了一个就应该把这个多的给来这边，继续保持数量上的平衡。

    1. class Solution {
    2. public:
    3.     vector<double> medianSlidingWindow(vector<int>& nums, int k) {
    4.         priority_queue<int> max_heap;
    5.         priority_queue<int, vector<int>, greater<int>> min_heap;
    8.         for(int i = 0; i < k; i++)
    9.             max_heap.push(nums[i]);
    11.         for(int i = 0; i < k/2; i++)
    12.         {
    13.             min_heap.push(max_heap.top());
    14.             max_heap.pop();
    15.         }
    17.         vector<double> res;
    18.         map<int, int> mp;
    19.         for(int i = k; i <= nums.size(); i++)
    20.         {
    21.             // cout << min_heap.top() << ' ' << max_heap.top() << endl;
    22.             res.push_back(k & 1? max_heap.top(): 0.5 * min_heap.top() + 0.5 * max_heap.top());
    23.             if(i == nums.size()) break;
    24.             int balance = 0;//这里容易错，删去max_heap，插入min_heap 这样balance = -2！
    25.             //其实是有几种情况的，1.删除和插入是max_heap 0   2.删除min插入max -2 3.删除max插入min 2  4.删除和插入都是min  0
    26.             balance += (nums[i - k] <= max_heap.top()? -1: 1);
    27.             mp[nums[i - k]]++;
    30.             if(nums[i] <= max_heap.top())
    31.             {
    32.                 max_heap.push(nums[i]);
    33.                 balance++;
    34.             }  
    35.             else
    36.             {
    37.                 min_heap.push(nums[i]);
    38.                 balance--;
    39.             }
    41.             if(balance > 0)
    42.             {
    43.                 min_heap.push(max_heap.top());
    44.                 max_heap.pop();
    47.             }
    48.             if(balance < 0)
    49.             {
    50.                 max_heap.push(min_heap.top());
    51.                 min_heap.pop();
    52.             }
    55.             while(max_heap.size() && mp[max_heap.top()] >= 1)
    56.             {
    57.                 mp[max_heap.top()]--;
    58.                 max_heap.pop();
    59.             }
    60.             while(min_heap.size() && mp[min_heap.top()] >= 1)
    61.             {
    62.                 mp[min_heap.top()]--;
    63.                 min_heap.pop();
    64.             }
    65.         }
    66.         return res;
    69.     }
    70. };

    第二次写题

    1. class Solution {
    2. public:
    3.     vector<double> medianSlidingWindow(vector<int>& nums, int k) {
    4.         vector<double> aRes;
    5.         priority_queue<int> aMaxHeap;
    6.         priority_queue<int, vector<int>, greater<int>> aMinHeap;
    7.         map<int, int> aDel;
    8.         for(int i = 0; i < k; i++)
    9.         {
    10.             aMaxHeap.push(nums[i]);
    11.         }
    12.         for(int i = 0; i < k/2; i++)
    13.         {
    14.             aMinHeap.push(aMaxHeap.top());
    15.             aMaxHeap.pop();
    16.         }
    17.         for(int i = k; i <= nums.size(); i++)
    18.         {
    19.             // cout << aMinHeap.top() << endl;
    20.             // cout << aMaxHeap.top() << endl;
    21.             // cout <<(double)aMinHeap.top() * 0.5 + (double)aMaxHeap.top() * 0.5 << endl;
    22.             aRes.push_back(k & 1? aMaxHeap.top():(double)aMinHeap.top() * 0.5 + (double)aMaxHeap.top() * 0.5);
    23.             if(i == nums.size()) break;
    25.             int balance = nums[i - k] <= aMaxHeap.top()? -1:1;
    26.             aDel[nums[i - k]]++;
    27.             if(nums[i] <= aMaxHeap.top()) 
    28.             {
    29.                 aMaxHeap.push(nums[i]);
    30.                 balance++;
    31.             }
    32.             else 
    33.             {
    34.                 aMinHeap.push(nums[i]);
    35.                 balance--;
    36.             }
    37.             if(balance < 0)
    38.             {
    39.                 aMaxHeap.push(aMinHeap.top());
    40.                 aMinHeap.pop();
    41.             }
    42.             else if(balance > 0)
    43.             {
    44.                 aMinHeap.push(aMaxHeap.top());
    45.                 aMaxHeap.pop();
    46.             }
    48.             while(aMaxHeap.size() && aDel[aMaxHeap.top()] > 0)
    49.             {
    50.                 aDel[aMaxHeap.top()]--;
    51.                 aMaxHeap.pop();
    52.             }
    53.             while(aMinHeap.size() && aDel[aMinHeap.top()] > 0)
    54.             {
    55.                 aDel[aMinHeap.top()]--;
    56.                 aMinHeap.pop();
    57.             }
    58.         }
    59.         return aRes;
    61.     }
    62. };