‍ 关于作者会编程的土豆“不是因为看见希望才坚持而是坚持了才看见希望。”你好我是会编程的土豆一名热爱后端技术的Java学习者。正在更新中的专栏《数据结构与算法》《leetcode hot 100》《数据库mysql》作者简介后端学习者例题例题#include queue #include functional using namespace std; class MedianFinder { private: // 大顶堆存较小的一半数字堆顶是这半的最大值 priority_queueint maxHeap; // 小顶堆存较大的一半数字堆顶是这半的最小值 priority_queueint, vectorint, greaterint minHeap; public: MedianFinder() { // 构造函数什么都不用做 } void addNum(int num) { // 核心规则 // 1. 新数先进大顶堆较小的一半 // 2. 把大顶堆的最大值移到小顶堆 // 3. 如果小顶堆比大顶堆大把小顶堆的最小值移回大顶堆 maxHeap.push(num); minHeap.push(maxHeap.top()); maxHeap.pop(); // 保持平衡maxHeap 的大小要么等于 minHeap要么比 minHeap 多 1 if (maxHeap.size() minHeap.size()) { maxHeap.push(minHeap.top()); minHeap.pop(); } } double findMedian() { // 根据两个堆的大小关系返回中位数 if (maxHeap.size() minHeap.size()) { // 奇数个元素中位数就是大顶堆的堆顶 return maxHeap.top(); } else { // 偶数个元素中位数是两个堆顶的平均值 return (maxHeap.top() minHeap.top()) / 2.0; } } }; /** * Your MedianFinder object will be instantiated and called as such: * MedianFinder* obj new MedianFinder(); * obj-addNum(num); * double param_2 obj-findMedian(); */数据流中位数MedianFinder详解为什么要用两个堆这道题很多人第一次看到会有点懵数据是不断加入的每次都要快速返回中位数如果你用最直接的方法每次插入后排序再取中位数复杂度是O(n log n)排序明显不行。一、核心问题我们要解决的是如何在“动态插入数据”的情况下快速找到中位数二、关键思路把数据分成两半我们可以这样想一半较小的数一半较大的数中位数就在这两部分的“交界处”。三、为什么用两个堆我们用两个堆来维护1. 大顶堆maxHeap存较小的一半堆顶是“较小部分的最大值”2. 小顶堆minHeap存较大的一半堆顶是“较大部分的最小值”这样如果总数是奇数 → 中位数就是 maxHeap.top()如果是偶数 → 中位数是两个堆顶的平均四、关键难点如何维持平衡必须保证maxHeap.size() minHeap.size()或maxHeap.size() minHeap.size() 1也就是说大顶堆最多比小顶堆多一个元素五、addNum 的核心逻辑重点来看代码void addNum(int num) { maxHeap.push(num); minHeap.push(maxHeap.top()); maxHeap.pop(); if(maxHeap.size() minHeap.size()) { maxHeap.push(minHeap.top()); minHeap.pop(); } }这段代码其实非常巧妙可以拆成三步理解第一步先把新元素丢进大顶堆maxHeap.push(num);先不管大小直接放进去。第二步把最大值丢到小顶堆minHeap.push(maxHeap.top()); maxHeap.pop();这一步的作用是保证 minHeap 里全是“较大的数”第三步重新平衡两个堆if(maxHeap.size() minHeap.size()) { maxHeap.push(minHeap.top()); minHeap.pop(); }如果小顶堆多了就把最小的那个“较大值”搬回来。六、为什么这样一定正确你可以这样理解整个过程每次插入先进入“小的那一半”maxHeap再把最大值送去“大的一半”minHeap最后调整数量这样可以保证maxHeap 里永远是较小的一半minHeap 里永远是较大的一半而且顺序始终正确。七、findMedian 就很简单了double findMedian() { if(maxHeap.size() minHeap.size()) { return maxHeap.top(); } else { return (maxHeap.top() minHeap.top()) / 2.0; } }两种情况1. 奇数个maxHeap 多一个中位数就是maxHeap.top()2. 偶数个两个堆一样多中位数(maxHeap.top() minHeap.top()) / 2八、时间复杂度插入O(log n)查询中位数O(1)相比排序效率提升非常明显。九、常见错误1. 顺序写反很多人会写成minHeap.push(num);这样会破坏结构。2. 没有保持大小关系必须保证maxHeap.size() minHeap.size()3. 忘记平衡少了这一步就会错if(maxHeap.size() minHeap.size())十、总结一句话这道题的本质就是用两个堆维护“中位数左右两边”保证数量平衡如果你再往上提升这道题还有进阶玩法支持删除变成滑动窗口中位数使用 multiset / 平衡树实现手写堆优化这些在面试中也非常常见。