LeetCode 295. 数据流的中位数——双堆动态维护的完整实现

适读人群：Java 中高级工程师、备战大厂面试的同学 | 阅读时长：约25分钟 | 难度：困难

---

开篇故事

如果说合并K链表是面试里被考得最多的「优先队列基础题」，那么数据流中位数就是被考得最多的「优先队列进阶题」。

这道题的难点不在于代码量，而在于设计思想：怎么用两个堆维护一个动态的、能快速查询中位数的数据结构？

我第一次做这道题时，下意识想到了有序数组——每次插入时二分找位置，O(log n) 找位置但 O(n) 移动元素，查询 O(1)。后来想到用链表，但链表查找 O(n)。

最后绕了一大圈，才明白：关键不是存整个有序序列，而是只需要维护「中间两个数」。用一个最大堆存较小的一半，一个最小堆存较大的一半，中位数就在两个堆顶之间。这个思路一旦想通，实现就很清晰了。

---

一、题目解析

题目描述：

实现 MedianFinder 类：

• MedianFinder() 初始化
• void addNum(int num) 从数据流中添加一个整数
• double findMedian() 返回目前所有元素的中位数

中位数定义：排序后中间的数（奇数个）或中间两个数的平均值（偶数个）。

示例：

MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3);    // arr = [1, 2, 3]
medianFinder.findMedian(); // 返回 2.0

---

二、解法一：有序动态数组

思路分析

维护一个有序数组，每次插入时二分找位置并插入，查询取中间元素。

import java.util.*;

class MedianFinder {
    private List<Integer> sorted;
    
    public MedianFinder() {
        sorted = new ArrayList<>();
    }
    
    public void addNum(int num) {
        // 二分找插入位置
        int left = 0, right = sorted.size();
        while (left < right) {
            int mid = (left + right) / 2;
            if (sorted.get(mid) < num) left = mid + 1;
            else right = mid;
        }
        sorted.add(left, num); // O(n) 移动
    }
    
    public double findMedian() {
        int n = sorted.size();
        if (n % 2 == 1) {
            return sorted.get(n / 2);
        } else {
            return (sorted.get(n / 2 - 1) + sorted.get(n / 2)) / 2.0;
        }
    }
}

复杂度分析

• addNum：O(n)。二分 O(log n)，但插入移动 O(n)。
• findMedian：O(1)。
• 空间复杂度：O(n)。

---

三、解法二：插入排序维护有序链表

这种解法复杂度更差（O(n) 找位置），这里不展开，直接进入最优解。

---

四、解法三（最优）：双堆

核心设计

维护两个堆：

• 大根堆 maxHeap（左堆）：存较小的一半，堆顶是其中最大的
• 小根堆 minHeap（右堆）：存较大的一半，堆顶是其中最小的

平衡条件：

• maxHeap.size() == minHeap.size()（偶数个元素）或
• maxHeap.size() == minHeap.size() + 1（奇数个元素，多出来的放左堆）

中位数：

• 偶数个：(maxHeap.peek() + minHeap.peek()) / 2.0
• 奇数个：maxHeap.peek()

插入逻辑（保持大根堆元素都 ≤ 小根堆元素，且大小平衡）：

完整代码

import java.util.*;

class MedianFinder {
    // 大根堆：存较小的一半
    private PriorityQueue<Integer> maxHeap;
    // 小根堆：存较大的一半
    private PriorityQueue<Integer> minHeap;
    
    public MedianFinder() {
        maxHeap = new PriorityQueue<>(Collections.reverseOrder()); // 大根堆
        minHeap = new PriorityQueue<>(); // 小根堆（默认）
    }
    
    public void addNum(int num) {
        // 先加入大根堆（保证插入的元素是 <= 大根堆已有最大值的那一半）
        // 再从大根堆把堆顶移到小根堆（保证大根堆的所有元素 <= 小根堆）
        maxHeap.offer(num);
        minHeap.offer(maxHeap.poll()); // 先平衡值域，确保 maxHeap.max <= minHeap.min
        
        // 然后平衡大小：小根堆不能比大根堆多
        if (minHeap.size() > maxHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }
    
    public double findMedian() {
        if (maxHeap.size() > minHeap.size()) {
            return maxHeap.peek(); // 奇数个，中位数是大根堆堆顶
        } else {
            return (maxHeap.peek() + minHeap.peek()) / 2.0; // 偶数个，平均值
        }
    }
}

手动模拟

操作	maxHeap（大根堆）	minHeap（小根堆）	中位数
add(1)	[1]	[]	1.0
add(2)	[1]	[2]	1.5
add(3)	[1,2] wait... 让我重新模拟

重新按照代码逻辑模拟 add(1):

1. maxHeap.offer(1) → maxHeap=[1]
2. minHeap.offer(maxHeap.poll()=1) → maxHeap=[], minHeap=[1]
3. minHeap.size(1) > maxHeap.size(0) → maxHeap.offer(minHeap.poll()=1) → maxHeap=[1], minHeap=[]

add(2):

1. maxHeap.offer(2) → maxHeap=[2,1]（大根堆顶是2）
2. minHeap.offer(maxHeap.poll()=2) → maxHeap=[1], minHeap=[2]
3. minHeap.size(1) == maxHeap.size(1)，不需要调整

findMedian: (1+2)/2.0 = 1.5 ✓

add(3):

1. maxHeap.offer(3) → maxHeap=[3,1]
2. minHeap.offer(maxHeap.poll()=3) → maxHeap=[1], minHeap=[2,3]
3. minHeap.size(2) > maxHeap.size(1) → maxHeap.offer(minHeap.poll()=2) → maxHeap=[2,1], minHeap=[3]

findMedian: maxHeap.size(2) > minHeap.size(1) → 返回 maxHeap.peek()=2 ✓

复杂度分析

• addNum：O(log n)。堆操作 O(log n)。
• findMedian：O(1)。直接查看堆顶。
• 空间复杂度：O(n)。

---

五、举一反三

双堆模式的变体：

题目	变体
295. 数据流中位数	本题，无窗口限制
480. 滑动窗口中位数	固定窗口 + 懒删除（下一篇）
4. 寻找两个正序数组的中位数	静态，二分 O(log min(m,n))

---

六、踩坑实录

坑一：整数相加求平均值时的精度问题

// 错误：整数除法，结果截断
return (maxHeap.peek() + minHeap.peek()) / 2;

// 正确：强转为 double 再除
return (maxHeap.peek() + minHeap.peek()) / 2.0;

(1 + 2) / 2 = 1（整数除），(1 + 2) / 2.0 = 1.5（浮点除）。

坑二：addNum 的「先移到小根堆再平衡大小」的两步操作不能颠倒

代码里的两步操作顺序很重要：

1. 先 maxHeap.offer(num); minHeap.offer(maxHeap.poll());——这一步保证「值域平衡」：大根堆的最大值 ≤ 小根堆的最小值
2. 再平衡大小

如果颠倒顺序，可能导致大根堆里有本该在小根堆里的较大值，破坏了两堆的值域分割。

坑三：大根堆用 Collections.reverseOrder()，不要手写 Comparator

// 正确：使用 Collections.reverseOrder()
new PriorityQueue<>(Collections.reverseOrder())

// 或者：
new PriorityQueue<>((a, b) -> b - a)

// 注意：(a, b) -> b - a 在 a=Integer.MIN_VALUE 时会溢出
// 安全写法：
new PriorityQueue<>((a, b) -> Integer.compare(b, a))

---

七、总结

数据流中位数是双堆设计模式的经典教材：

• 大根堆存较小一半，小根堆存较大一半
• 维护两个不变量：值域分割（左堆最大 ≤ 右堆最小）和大小平衡（左堆不小于右堆）
• addNum 时通过「先统一入一个堆再移堆顶到另一个堆」来同时保持两个不变量

这个双堆模式是动态中位数问题的标准解法，理解透了下一题（滑动窗口中位数）就容易了很多。