题解 | #栈的压入、弹出序列#

【问题描述】

• 如何得到一个数据流中的中位数？
• 如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。
• 如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

【解题思路】

• 构建两个堆分别存储中位数两边的值，左边构建为大顶堆，右边构建为小顶堆。
• 插入元素时：
• N 为偶数时要插入到右半边
• 因为右半边元素要大于左半边，但是新插入的元素不一定比左半边元素大，
• 因此需要先将元素插入到左边，利用左边是大堆顶的特点，
• 取出堆顶即为最大元素，此时插入右边。
• N 为奇数时操作同理
• 取出中位数时：
• 这样当输入数的数量为偶数时，同时取出左右两边的堆顶相加除以2即可
• 当输入数的数量为奇数时，取出右边的堆顶元元素即可，

【代码示例】
// 大顶堆存储左半边元素
private PriorityQueue<integer> maxLeft = new PriorityQueue<>((o1, o2) -> o2 -o1);
// 小顶堆存储右半边元素
private PriorityQueue<integer> minRight = new PriorityQueue<>();
// 当前数据流读入的元素个数
private int N = 0;</integer></integer>

public void insert(Integer val) {
    // 插入元素时要保证两个堆处于平衡状态
    if (N % 2 == 0) {
        /*
         * N 为偶数时要插入到右半边
         * 因为右半边元素要大于左半边，但是新插入的元素不一定比左半边元素大，
         * 因此需要先将元素插入到左边，利用左边是大堆顶的特点，
         * 取出堆顶即为最大元素，此时插入右边。
         */
        maxLeft.add(val);
        minRight.add(maxLeft.poll());
    } else {
        minRight.add(val);
        maxLeft.add(minRight.poll());
    }
    N++;
}

public Double getMedian() {
    if (N % 2 == 0) {
        return (maxLeft.peek() + minRight.peek()) / 2.0;
    } else {
        return Double.valueOf(minRight.peek());
    }
}