一. 题目

二. 思路

1. 对顶堆

小根堆较大的数，大根堆存较小的数，大根堆的最大值小于小根堆的最小值。
两堆的数量差不能超过1。
优先加小根堆，当数量差1，则小根堆堆顶就是中位数，当数量相等，则大小根堆堆顶和除以2。
注意维护性质1

2. 有序集合+双指针

三. 代码

1. 对顶堆

class MedianFinder
{
    Queue<Integer> minQ = new PriorityQueue<>();
    Queue<Integer> maxQ = new PriorityQueue<>(Comparator.reverseOrder());

    public MedianFinder()
    {
        minQ.clear();
        maxQ.clear();
    }

    public void addNum(int num)
    {
        if (minQ.size() == maxQ.size())
        {
            if (minQ.isEmpty()) minQ.offer(num);
            else
            {
                int maxV = maxQ.peek();
                if (num < maxV)
                {
                    minQ.offer(maxQ.poll());
                    maxQ.offer(num);
                } else minQ.offer(num);
            }
        } else if (minQ.size() > maxQ.size())
        {
            int minV = minQ.peek();
            if (num > minV)
            {
                maxQ.offer(minQ.poll());
                minQ.offer(num);
            } else maxQ.offer(num);
        }
    }

    public double findMedian()
    {
        if (minQ.size() == maxQ.size()) return (minQ.peek() + maxQ.peek()) / 2.0;
        return (double) minQ.peek();
    }
}