题解 | #售价的中位数#

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

这道题目主要考察了以下知识点：

1. 使用最大堆和最小堆来维护动态数据流中的中位数，以及如何通过调整堆的大小和堆顶元素来实现。
2. 堆的操作和优先队列的使用。
3. 处理动态数据流问题的思路。

题目解答方法的文字分析

这个问题可以看作是一个实时更新中位数的过程，而不是在静态数组中找中位数。我们可以通过使用两个堆来实现。最大堆用于存放较小的一半数，最小堆用于存放较大的一半数。这样，中位数可以通过堆顶元素来得到。

下面是一个详细的步骤分析：

1. 创建一个最大堆 maxHeap 和一个最小堆 minHeap。
2. 遍历价格数组，依次将价格插入到合适的堆中，保持两个堆的大小差距不超过1，并且最大堆的堆顶小于等于最小堆的堆顶。
3. 如果最大堆的大小比最小堆大1，那么中位数就是最大堆的堆顶元素。如果两个堆大小相等，中位数就是两个堆的堆顶元素之和除以2。
4. 在插入价格时，需要根据大小关系选择插入到最大堆还是最小堆。如果插入到最大堆，需要将最大堆的堆顶元素弹出并插入到最小堆中，保持两个堆的平衡

本题解析所用的编程语言

本题解析所用的编程语言是C++。

完整且正确的编程代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param prices int整型vector 
     * @return double浮点型vector
     */
    vector<double> findMedianPrice(vector<int>& prices) {
        priority_queue<int, vector<int>, less<int>> maxHeap; // 最大堆
        priority_queue<int, vector<int>, greater<int>> minHeap; // 最小堆
        
        vector<double> medians;
        
        for (int price : prices) {
            if (maxHeap.empty() || price <= maxHeap.top()) {
                maxHeap.push(price);
            } else {
                minHeap.push(price);
            }
            
            // 调整堆的大小
            if (maxHeap.size() > minHeap.size() + 1) {
                minHeap.push(maxHeap.top());
                maxHeap.pop();
            } else if (maxHeap.size() < minHeap.size()) {
                maxHeap.push(minHeap.top());
                minHeap.pop();
            }
            
            // 计算中位数
            if (maxHeap.size() > minHeap.size()) {
                medians.push_back(maxHeap.top());
            } else {
                medians.push_back((double)(maxHeap.top() + minHeap.top()) / 2.0);
            }
        }
        
        return medians;
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！