大厂面试真题详解：滑动窗口的中位数

给定一个包含 n 个整数的数组，和一个大小为 k 的滑动窗口,从左到右在数组中滑动这个窗口，找到数组中每个窗口内的中位数。(如果数组个数是偶数，则在该窗口排序数字后，返回第 N/2 个数字。)

在线评测地址：领扣题库官网

样例 1:

输入:
[1,2,7,8,5]
3
输出:
[2,7,7]

解释:
最初，窗口的数组是这样的：[ | 1,2,7 | ,8,5] , 返回中位数 2;
接着，窗口继续向前滑动一次。[1, | 2,7,8 | ,5], 返回中位数 7;
接着，窗口继续向前滑动一次。[1,2, | 7,8,5 | ], 返回中位数 7;

样例 2:

输入:
[1,2,3,4,5,6,7]
4
输出:
[2,3,4,5]

解释:
最初，窗口数组是这样的：[ | 1,2,3,4, | 5,6,7] , 返回中位数 2;
接着，窗口向前滑动一次.[1,| 2,3,4,5 | 6,7],返回中位数 3;
接着，窗口向前滑动一次.[1,2, | 3,4,5,6 | 7 ], 返回中位数 4;
接着，窗口向前滑动一次[1,2,3,| 4,5,6,7 ], 返回中位数 5;

题解：
使用九章算法强化班中讲到的 HashHeap。即一个 Hash + Heap。 Hash 的 key 是 Heap 里的每个元素，值是这个元素在 Heap 中的下标。

要做这个题首先需要先做一下 Data Stream Median。这个题是只在一个集合中增加数，不删除数，然后不断的求中点。 Sliding Window Median，就是不断的增加数，删除数，然后求中点。比 Data Stream Median 难的地方就在于如何支持删除数。

因为 Data Stream Median 的方法是用 两个 Heap，一个 max heap，一个min heap。所以删除的话，就需要让 heap 也支持删除操作。 由于 Python 的 heapq 并不支持 logn 时间内的删除操作，因此只能自己实现一个 hash + heap 的方法。

总体时间复杂度 O(nlogk)，n是元素个数，k 是 window 的大小。

    public class Solution {
        /*
         * @param nums: A list of integers
         * @param k: An integer
         * @return: The median of the element inside the window at each moving
         */
        PriorityQueue<Integer> maxHeap, minHeap;
        public List<Integer> medianSlidingWindow(int[] A, int k) {
            // write your code here
            List<Integer> res = new ArrayList<Integer>();
            int n = A.length;
            if (n == 0) {
                return res;
            }
            
            maxHeap = new PriorityQueue<Integer>(n, Collections.reverseOrder());
            minHeap = new PriorityQueue<Integer>(n);
            
            int i;
            for (i = 0; i < n; ++i) {
                if (maxHeap.size() == 0 || A[i] <= maxHeap.peek()) {
                    maxHeap.offer(A[i]);
                }
                else {
                    minHeap.offer(A[i]);
                }
                
                balance();
                if (i - k >= 0) {
                    if (A[i - k] > maxHeap.peek()) {
                        minHeap.remove(A[i - k]);
                    }
                    else {
                        maxHeap.remove(A[i - k]);
                    }
                }
                
                balance();
                
                if (i >= k - 1) {
                    res.add(maxHeap.peek());
                }
            }
            
            return res;
        }
        
        private void balance() {
            while (maxHeap.size() < minHeap.size()) {
                maxHeap.offer(minHeap.poll());
            }
            
            while (minHeap.size() < maxHeap.size() - 1) {
                minHeap.offer(maxHeap.poll());
            }
        }
    }

更多题解参考：九章官网solution