题解 | 数据流中的中位数

import java.util.*;


public class Solution {

    PriorityQueue<Integer> minQueue = new PriorityQueue<>();
    PriorityQueue<Integer> maxQueue = new PriorityQueue<>(Collections.reverseOrder());

    public void Insert(Integer num) {
        //1. 假设第一个5 第二个2 ，全部放到了最大堆
        //2. 两个元素已经超过了最小堆的0个元素，所以把最大堆的堆顶5放到了最小堆
        //3. 这样子就会出现 最大堆的堆顶就是 中位数 或者 最小堆的堆顶就是中位数
        if (maxQueue.isEmpty() || num <= maxQueue.peek()) {
            maxQueue.offer(num);
        } else {
            minQueue.offer(num);
        }

        if (maxQueue.size() > minQueue.size() + 1) {
            minQueue.offer(maxQueue.poll());
        } else if (maxQueue.size() < minQueue.size()) {
            maxQueue.offer(minQueue.poll());
        }
    }

    public Double GetMedian() {
        if (maxQueue.size() == minQueue.size()) {
            // 偶数个
            return (maxQueue.peek() + minQueue.peek()) / 2.0;
        } else {
            // 奇数个
            return (double)maxQueue.peek();
        }
    }


}