目录
1、 1046. 最后一块石头的重量
2、 703. 数据流中的第 K 大元素
为什么小根堆可以解决TopK问题？
3、 692. 前K个高频单词
4、 295. 数据流的中位数
1、 1046. 最后一块石头的重量
思路：根据示例发现可以用大根堆(降序)模拟这个过程。
class Solution {
public:int lastStoneWeight(vector<int>& stones) {priority_queue<int> heap;for (auto s : stones)heap.push(s);while (heap.size() > 1) {int a = heap.top();heap.pop();int b = heap.top();heap.pop();if (a > b)heap.push(a - b);}return heap.size() ? heap.top() : 0;}
};2、 703. 数据流中的第 K 大元素
思路：TopK问题使用小根堆堆解决，priority_queue（默认大根堆）的第三个参数为greater<类型>即为小根堆。
class KthLargest {
public:int _k;priority_queue<int, vector<int>, greater<int>> heap;KthLargest(int k, vector<int>& nums) {_k = k;for (auto n : nums) {heap.push(n);if (heap.size() > _k)heap.pop();}}int add(int val) {heap.push(val);if (heap.size() > _k)heap.pop();return heap.top();}
};/*** Your KthLargest object will be instantiated and called as such:* KthLargest* obj = new KthLargest(k, nums);* int param_1 = obj->add(val);*/为什么小根堆可以解决TopK问题？
对于设计一个找到数据流中第k大元素的类的问题，我们应该使用小根堆（Min Heap）来实现。下面解释为什么使用小根堆以及如何使用它：
-
为什么使用小根堆:
- 小根堆能够保证堆顶元素是堆中最小的元素。在维护数据流中的第k大元素时，我们希望能够快速访问到第k大的元素，而不是最小的元素。通过维护一个大小为k的小根堆，堆中的元素就是数据流中最大的k个元素，而堆顶元素（最小元素）就是这k个元素中第k大的元素。
- 当新的元素加入时，如果它大于堆顶元素，我们就将它加入堆中，并移除堆顶元素，这样堆的大小仍然保持为k。这样做可以确保堆中始终是数据流中最大的k个元素，而堆顶元素就是这些元素中最小的，即第k大的元素。
-
如何使用小根堆:
- 初始化时，将数组
nums中的元素加入小根堆中，如果元素数量超过k，则移除堆顶元素，以保证堆的大小为k。 - 对于
add方法，每次加入一个新元素时，先将其加入到小根堆中。如果加入后堆的大小超过k，则移除堆顶元素。然后返回堆顶元素，即为当前数据流中第k大的元素。
- 初始化时，将数组
通过使用小根堆，我们可以高效地解决数据流中的第k大元素问题，同时保证时间复杂度和空间复杂度都在合理的范围内。
3、 692. 前K个高频单词
思路：
- 频次统计：首先，使用哈希表记录每个单词出现的频次。
- 优先队列排序：利用优先队列（或小根堆）根据单词的频次和字典序排序，从而找出频次最高的前
k个单词。实现步骤
处理单词列表：
- 利用哈希表统计每个单词出现的次数，确保单词不会重复计数且记录了它们的频次。
使用小根堆选择前 k 大元素：
- 根据问题要求，设计比较器（cmp）：
- 频次不同：频次较少的优先（小根堆性质）。
- 频次相同：字典序较小的优先（大根堆性质）。
- 使用优先队列（小根堆）存储单词及其频次，保证堆的大小不超过
k。- 将每个单词和它的频次插入到堆中，如果堆的大小超过了
k，就移除堆顶元素。获取结果：
- 最终，堆中剩余的就是频次最高的前
k个单词。反向遍历堆，将元素按正确的顺序存入结果列表中。
class Solution {
public:typedef pair<string,int> PSI;struct cmp{bool operator()(const PSI& a,const PSI& b){if(a.second==b.second){return a.first<b.first;}return a.second>b.second;}};vector<string> topKFrequent(vector<string>& words, int k) {unordered_map<string,int> hash;for(auto& s:words)hash[s]++;priority_queue<PSI,vector<PSI>,cmp> heap;for(auto& psi:hash){heap.push(psi);if(heap.size()>k)heap.pop();}vector<string> ret(k);for(int i=k-1;i>=0;i--){ret[i]=heap.top().first;heap.pop();}return ret;}
};4、 295. 数据流的中位数
实现一个动态中位数查找器
动态数据流中位数查找是一种常见问题，可以通过聪明地运用数据结构来解决。以下是如何通过维护两个堆：一个大根堆和一个小根堆—来实现一个动态中位数查找器的步骤。
解决方法：利用两个堆
算法思路
本解法是一个关于堆数据结构的经典应用。通过将数据流平分或近似平分为两个部分：一个较小部分和一个较大部分—可以高效解决问题：
较小的部分在大根堆（
left）中。较大的部分在小根堆（
right）中。如此设置允许我们在常数时间内获得中位数。
动态添加数据
我们需要保证left比right大1或者left等于right，这样才能算出中位数，当有新数据加入时，进行以下步骤以保持两个堆的平衡：
两个堆的大小相同 (
left.size() == right.size()):
若堆为空，直接将 num 放入
left中。若 num
<= left.top()，将x放入left。否则，先将 num 放入
right，再将right的堆顶元素移到left中。两个堆的大小不相同 (
left.size() > right.size()+1):
若
num小于或等于 left.top()，再将left的堆顶元素移到right中。否则，将
num放入 right，查找中位数
若两个堆的大小相同，中位数是两个堆顶元素的平均值。
- 否则，中位数是
left堆的顶元素。
class MedianFinder
{priority_queue<int> left; // 大根堆priority_queue<int, vector<int>, greater<int>> right; // 小根堆public:MedianFinder() {}void addNum(int num){// 分类讨论即可if(left.size() == right.size()) // 左右两个堆的元素个数相同{if(left.empty() || num <= left.top()) // 放 left 里面{left.push(num);}else{right.push(num);left.push(right.top());right.pop();}}else{if(num <= left.top()){left.push(num);right.push(left.top());left.pop();}else{right.push(num);}}}double findMedian(){if(left.size() == right.size()) return (left.top() + right.top()) / 2.0;else return left.top();}
};
