题解 | #售价的中位数# 对顶堆

知识点

对顶堆

思路

动态维护中位数。可以搞两个堆，一个是较小的一半数（大顶堆），一个是较大的一半数（小顶堆），较小元素的堆至多比较大元素的堆多一个元素。这样每次求中位数，要么是小数堆的堆顶，要么是小数堆和大数堆的堆顶的平均数，单次时间复杂度为。

然后考虑如何维护这两个堆。每次我们加入一个新的元素，先加入大顶堆，然后假如大顶堆的堆顶大于小顶堆的堆顶元素（就是刚才加入那个数比较大），调换两个堆的堆顶。之后假如小数的堆个数比大数的堆多两个元素以上了，需要调一个元素过去。单次维护的时间复杂度是。

一共进行n次，总的时间复杂度为。

AC code（C++）

#include <queue>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param prices int整型vector 
     * @return double浮点型vector
     */
    vector<double> findMedianPrice(vector<int>& prices) {
        // 两个堆
        vector<double> res;
        priority_queue<int, vector<int>, greater<>> r;
        priority_queue<int> l;
        int n = prices.size();
        for (int i = 0; i < n; i ++) {
            l.push(prices[i]);
            if (r.size() and l.top() > r.top()) {
                auto t1 = l.top();
                l.pop();
                auto t2 = r.top();
                r.pop();
                l.push(t2), r.push(t1);
            }
            if (l.size() - r.size() == 2) {
                r.push(l.top());
                l.pop();
            }

            if (i & 1) {
                res.push_back(0.5 * (l.top() + r.top()));
            }
            else res.push_back(1.0 * l.top());
        }
        return res;
    }
};