295. 数据流的中位数

难度：🔴 Hard | 标签：堆、设计 | 状态：⬜ LeetCode 链接

思路

双堆：

• 大顶堆 lo 装较小一半
• 小顶堆 hi 装较大一半
• 保持 |lo| - |hi| ∈ {0, 1}

addNum 时先入 lo，再把 lo 顶移到 hi；若 hi 比 lo 多一个，把 hi 顶回 lo。

代码

class MedianFinder {
    priority_queue<int> lo;                                   // max heap
    priority_queue<int, vector<int>, greater<int>> hi;        // min heap
public:
    void addNum(int num) {
        lo.push(num);
        hi.push(lo.top()); lo.pop();
        if (hi.size() > lo.size()) { lo.push(hi.top()); hi.pop(); }
    }
    double findMedian() {
        if (lo.size() > hi.size()) return lo.top();
        return (lo.top() + hi.top()) / 2.0;
    }
};

复杂度

• addNum O(log n)，findMedian O(1)
• 空间 O(n)

易错 / 回顾

• 流程：「lo 入再倒」+「hi 多则回 lo」，保证 lo ≥ hi
• 奇数总数答案取 lo 顶
• 返回值用 2.0 避免整数除