题解 | #数据流中的中位数#

import java.util.*;


public class Solution {

    PriorityQueue<Integer> larger, smaller;

    public Solution() {
        // smaller 保留较小的元素, 保证 larger.size() >= smaller.size()
        smaller = new PriorityQueue<>((a, b) -> b.compareTo(a));
        larger = new PriorityQueue<>();
    }

    public void Insert(Integer num) {
        if(larger.size() == smaller.size()) {
            // 向 larger 中添加元素
            if(larger.isEmpty() || smaller.peek() <= num) {
                larger.offer(num);
            } else {
                // smaller.peek() > num
                larger.offer(smaller.poll());
                smaller.offer(num);
            }
        } else {
            // 向 smaller 中添加元素
            if(larger.peek() >= num) {
                smaller.offer(num);
            } else {
                // larger.peek() < num
                smaller.offer(larger.poll());
                larger.offer(num);
            }
        }
    }

    public Double GetMedian() {
        return larger.size() == smaller.size() ? Double.valueOf((larger.peek() + smaller.peek()) / 2.0) : Double.valueOf(larger.peek());
    }


}