Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples:
<code>[2,3,4]</code> , the median is <code>3</code>

<code>[2,3]</code>, the median is <code>(2 + 3) / 2 = 2.5</code>

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Your job is to output the median array for each window in the original array.

For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Therefore, return the median sliding window as <code>[1,-1,-1,3,5,6]</code>.

解題思路

這道題讓我想起來之前微軟的的一道面試題。給一個數列，求出前k個數的中位數（k=1,2,..,n）。這道題的解法是這樣的：

維護兩個堆：一個大根堆，一個小根堆。大根堆存放較小的那些數，小根堆存放較大的那些數。在兩個堆大小差距不超過1的情況下，很容易求得中位數。堆的具體維護方法如下：

Step 1：對于每一個新加的數，若小于大根堆的堆頂，則放入大根堆，反之放入小根堆。
Step 2：平衡兩個堆。分別用兩個數值記錄每個隊中的元素個數，將元素個數多的堆的堆頂元素移入元素個數少的堆，直至兩個堆的元素個數差不超過1
Step 3：求出此時的中位數

兩道題非常的相似，唯一不同的是多了一個滑動窗。而且由于堆的特性，不能隨便刪除堆中元素（要從堆頂刪），似乎就不能用上面的方法做了。然而真的是這樣嗎？

先看代碼：

class Solution {
public:
    vector<double> medianSlidingWindow(vector<int>& nums, int k) {
        vector<double> medians;
        unordered_map<int, int> hash;                          // count numbers to be deleted
        priority_queue<int, vector<int>> bheap;                // heap on the bottom
        priority_queue<int, vector<int>, greater<int>> theap;  // heap on the top
        
        int i = 0;
        
        // Initialize the heaps
        while (i < k)  { bheap.push(nums[i++]); }
        for (int count = k/2; count > 0; --count) {
            theap.push(bheap.top()); bheap.pop();
        }
        
        while (true) {
            // Get median
            if (k % 2) medians.push_back(bheap.top());
            else medians.push_back( ((double)bheap.top() + theap.top()) / 2 );
            
            if (i == nums.size()) break;
            int m = nums[i-k], n = nums[i++], balance = 0;
            
            // What happens to the number m that is moving out of the window
            if (m <= bheap.top())  { --balance;  if (m == bheap.top()) bheap.pop(); else ++hash[m]; }
            else                   { ++balance;  if (m == theap.top()) theap.pop(); else ++hash[m]; }
            
            // Insert the new number n that enters the window
            if (!bheap.empty() && n <= bheap.top())  { ++balance; bheap.push(n); }
            else                                     { --balance; theap.push(n); }
            
            // Rebalance the bottom and top heaps
            if      (balance < 0)  { bheap.push(theap.top()); theap.pop(); }
            else if (balance > 0)  { theap.push(bheap.top()); bheap.pop(); }
            
            // Remove numbers that should be discarded at the top of the two heaps
            while (!bheap.empty() && hash[bheap.top()])  { --hash[bheap.top()]; bheap.pop(); }
            while (!theap.empty() && hash[theap.top()])  { --hash[theap.top()]; theap.pop(); }
        }
        
        return medians;
    }
};

我們可以看到，作者引入了一個有效數目概念，當一個元素被刪除時，我們判定他為無效。在衡量兩個堆大小時，比較兩個堆的有效數目大小，再進行調整。而且，由于堆頂元素一定是有效的（最后一步會清除無效的堆頂元素），在調整時，最多只需要調整一個元素。

由此來看，此題是微軟面試題的變種。在應付中位數問題時，兩個堆的做法一般是實用而高效的，只是需要進行靈活變通。