数据流的中位数 leetcode 295.

题目大意：给定一个数据流，实现一个以查找中位数为方法的类，该类需要有初始化构造方法、新增数据值和查找中位数的方法
解题思路：主要难点是想用什么方法，这题肯定不能来一个数字就给数据排序，得用到数据结构，也就是小顶堆和大顶堆，小顶堆存储最大值部分，大顶堆存储最小值部分，默认以小顶堆多一个（如果出现数据流长度为奇数堆的情况下），这里有一个滑动入值的概念，当两个堆大小不一致时，肯定是小顶堆多于大顶堆了，这时候我得先将该新数字放进小顶堆中过滤（排序）一遍后再将新的小顶堆的堆顶取出来放到大顶堆中去，这样就不会破坏小顶堆的值是大于大顶堆的值的原则，且是排序了的。当两个堆大小一致时，同理。查找中位数的话就是判断是否大小一致，如果两个堆大小一致就说明是偶数，那就将两个堆堆顶拿到/2就可以了，不一致的话我们设定了小顶堆的大小是>=大顶堆的，所以直接拿出小顶堆的堆顶即可。

class MedianFinder {

    Queue<Integer> A,B;

    public MedianFinder() {
        A = new PriorityQueue<>();
        B = new PriorityQueue<>((a, b) -> (b - a));
    }
    
    public void addNum(int num) {
        if(A.size() != B.size()) {
            A.add(num);
            B.add(A.poll());
        } else{
            B.add(num);
            A.add(B.poll());
        }
    }
    
    public double findMedian() {
        return A.size() == B.size() ? (A.peek() + B.peek()) / 2.0 : A.peek() * 1.0;
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

总结：对于困难类型的题目一开始还是不能被吓到，要敢于思考想想所学的数据结构有哪些能帮到解决该题目，主要还是这些数据结构运用的不够熟练，思路其实很清晰了