数据流中位数与滑动窗口中位数

数据流的中位数（LeetCode 295）

动态数据流中，随时获取中位数。

双堆设计

• maxHeap（大根堆）：存较小的一半，堆顶是最大值
• minHeap（小根堆）：存较大的一半，堆顶是最小值
• 维护：两堆大小差不超过 1；maxHeap.size() >= minHeap.size()

class MedianFinder {
    private PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    private PriorityQueue<Integer> minHeap = new PriorityQueue<>();

    public void addNum(int num) {
        maxHeap.offer(num);
        minHeap.offer(maxHeap.poll());          // 先给大根堆，再调整
        if (maxHeap.size() < minHeap.size()) {   // 保持 max >= min 大小
            maxHeap.offer(minHeap.poll());
        }
    }

    public double findMedian() {
        if (maxHeap.size() > minHeap.size()) {
            return maxHeap.peek();
        }
        return (maxHeap.peek() + minHeap.peek()) / 2.0;
    }
}

时间：添加 O(log n)，查询 O(1)。

滑动窗口中位数（LeetCode 480）

固定大小窗口，每次滑动后求中位数。

难点：需要 O(log n) 删除任意元素。Java PriorityQueue 不支持 O(log n) 删除。

解法：延迟删除（懒删除）

用 HashMap 标记"待删除"的元素，在堆顶时再真正删除。

public double[] medianSlidingWindow(int[] nums, int k) {
    PriorityQueue<Integer> maxH = new PriorityQueue<>(Collections.reverseOrder());
    PriorityQueue<Integer> minH = new PriorityQueue<>();
    Map<Integer, Integer> delayed = new HashMap<>();
    double[] res = new double[nums.length - k + 1];

    // 初始化窗口
    for (int i = 0; i < k; i++) {
        maxH.offer(nums[i]);
    }
    for (int i = 0; i < k / 2; i++) {
        minH.offer(maxH.poll());
    }

    for (int i = k; i <= nums.length; i++) {
        res[i - k] = k % 2 == 0
            ? ((double) maxH.peek() + minH.peek()) / 2
            : maxH.peek();

        if (i == nums.length) break;

        int inNum = nums[i], outNum = nums[i - k];
        // 将旧元素标记为待删除
        delayed.merge(outNum, 1, Integer::sum);

        // 新元素加入
        if (inNum <= maxH.peek()) maxH.offer(inNum);
        else minH.offer(inNum);

        // 平衡
        // 大根堆多 => 移一个到小根堆
        if (maxH.size() - minH.size() > (k % 2 == 1 ? 1 : 0)) {
            minH.offer(maxH.poll());
        } else if (minH.size() > maxH.size()) {
            maxH.offer(minH.poll());
        }

        // 懒删除：清理堆顶无效元素
        while (!maxH.isEmpty() && delayed.getOrDefault(maxH.peek(), 0) > 0) {
            delayed.merge(maxH.poll(), -1, Integer::sum);
        }
        while (!minH.isEmpty() && delayed.getOrDefault(minH.peek(), 0) > 0) {
            delayed.merge(minH.poll(), -1, Integer::sum);
        }
    }
    return res;
}

对比