題目描述

設計數據結構支持兩操作：

• addNum(int num)：從數據流添加整數
• findMedian()：返回當前所有元素中位數

中位數定義：有序列表中間值；偶數個元素取中間兩數平均值。例如 [2,3,4] → 3，[2,3] → 2.5。

核心思想：大根堆 + 小根堆

• maxHeap（大根堆）：存較小一半元素，堆頂為最大值
• minHeap（小根堆）：存較大一半元素，堆頂為最小值
• 不變量：maxHeap.size() == minHeap.size() 或 maxHeap.size() == minHeap.size() + 1
• 中位數：
  • 尺寸相等：(maxHeap.top() + minHeap.top()) / 2.0
  • 尺寸不等：maxHeap.top()（規定 maxHeap 多一個）

添加元素邏輯

1. 新元素先入 minHeap
2. 將 minHeap 堆頂移至 maxHeap
3. 若 maxHeap 尺寸超過 minHeap + 1，將 maxHeap 堆頂移回 minHeap

這樣保證：所有 maxHeap 元素 ≤ 所有 minHeap 元素，且尺寸平衡。

完整代碼

// C++ Runtime: 212 ms
class MedianFinder {
    priority_queue<int> maxHeap; // 大根堆（默認）
    priority_queue<int, vector<int>, greater<int>> minHeap; // 小根堆
public:
    void addNum(int num) {
        minHeap.push(num);
        maxHeap.push(minHeap.top()); minHeap.pop();
        if (maxHeap.size() > minHeap.size() + 1) {
            minHeap.push(maxHeap.top()); maxHeap.pop();
        }
    }
    double findMedian() {
        if (maxHeap.size() == minHeap.size())
            return (maxHeap.top() + minHeap.top()) / 2.0;
        else
            return maxHeap.top();
    }
};

// Java Runtime: 50 ms
class MedianFinder {
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    public void addNum(int num) {
        minHeap.offer(num);
        maxHeap.offer(minHeap.poll());
        if (maxHeap.size() > minHeap.size())
            minHeap.offer(maxHeap.poll());
    }
    public double findMedian() {
        if (maxHeap.size() == minHeap.size())
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        else
            return maxHeap.peek();
    }
}

複雜度分析

• addNum：O(log n) 堆操作
• findMedian：O(1) 僅訪問堆頂
• 空間：O(n) 存儲所有元素

擴展：數據流中位數變體

• 滑動窗口中位數：需支持刪除，用雙平衡 BST（multiset/TreeMap）或延遲刪除堆
• 加權中位數：堆中存 (值, 權重) 對，維護前綴權重和