题解 | #随时找到数据流的中位数#

大/小顶堆

class MedianHolder{
private:
    priority_queue<int, vector<int>, less<int>> maxPq; //放小的一半，奇数个数时，比minPq多一个元素
    priority_queue<int, vector<int>, greater<int>> minPq; //放大的一半
public:
    void put(int val){
        if(maxPq.si***Pq.si***Pq.push(val);
            int value = minPq.top(); minPq.pop();
            maxPq.push(value);
        }else{
            maxPq.push(val);
            int value = maxPq.top(); maxPq.pop();
            minPq.push(value);
        }

    }
    double get(){
        if(maxPq.empty() && minPq.empty()) return -1;
        if(maxPq.si***Pq.size()){
            double valA = maxPq.top();
            double valB = minPq.top();
            return (valA + valB) / 2;
        }else{
            return maxPq.top();
        }
    }
};

class Solution {
public:

    /**
     * the medians
     * @param operations int整型vector<vector<>> ops
     * @return double浮点型vector
     */
    vector<double> flowmedian(vector<vector<int> >& operations) {
        // write code here
        vector<double> res;
        MedianHolder medianHolder;
        for(vector<int> op:operations){
            if(op[0] == 1){
                medianHolder.put(op[1]);
            }else{
                res.push_back(medianHolder.get());
            }
        }
        return res;
    }
};