1.最后一块石头的重量
其实就是一个模拟的过程：每次从石堆中拿出最大的元素以及次大的元素，然后将它们粉碎；如果还有剩余，就将剩余的石头继续放在原始的石堆里面重复上面的操作，直到石堆里面只剩下一个元素，或者没有元素(因为所有的石头可能全部抵消了)，那么主要的问题就是解决：如何顺利的拿出最大的石头以及次大的石头；并且将粉碎后的石头放入石堆中之后，也能快速找到下一轮粉碎的最大石头和次大石头。我们一看到这个就会说，这行呀！找最大值，我直接排序加遍历就行了，但是此时石头粉碎之后，如果此时还有值，我们就要插入这个值，排序就乱了，我们还需要重新插入 + 排序，复杂度较大。我们仔细想一下，这不正好可以利用堆的特性来实现嘛?我们可以创建一个 大根堆；然后将所有的石头放入大根堆中;每次拿出前两个堆顶元素粉碎一 下，如果还有剩余，就将剩余的石头继续放入堆中；这样就能快速的模拟出这个过程，直接上思路：
直接上代码：
class Solution {
public:
int lastStoneWeight(vector<int>& stones) {
// 1.创建⼀个⼤根堆
priority_queue<int> heap;
// 2.将所有元素丢进这个堆⾥⾯
for (auto x : stones)
heap.push(x);
// 3.模拟这个过程
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.数据流中的第K大元素
我相信找第K大元素，就能想到TopK问题，兄弟们应该能立马想到「堆」， 这应该是刻在骨子里的记忆，只不过我们要知道找第K大元素我们需要建立小堆，我们要想想，如果我们弄一个大堆，如果第一个元素就是数组中最大的元素，那么此时其他元素如何入堆，哪还找什么第k的元素呢？这里还有一个细节，由于默认的堆是大堆，所以我们这里要传入仿函数，直接上思路：
直接上代码：
class KthLargest {
public:
KthLargest(int k, vector<int>& nums) {
_k = k;
for(auto x : nums)
{
heap.push(x);
if(heap.size() > _k) heap.pop();
}
}
int add(int val) {
heap.push(val);
if(heap.size() > _k) heap.pop();
return heap.top();
}
private:
priority_queue<int,vector<int>,greater<int>> heap;
int _k;
};3.前K个高频单词
首先我们看到这个题目，就能想到TopK问题，兄弟们应该能立马想到「堆」， 这应该是刻在骨子里的记忆，直接上思路：
直接上代码：
class Solution {
struct cmp{
bool operator()(const pair<string,int>& a, const pair<string,int>& b)
{
if(a.second == b.second) // 频次相同的时候:需要的是基于字典序⽐较的⼤根堆
// 谁小谁往下
return a.first < b.first;
// 谁大谁往下
return a.second > b.second; //频次不同的时候:需要的是基于频次⽐较的⼩根堆
}
};
public:
vector<string> topKFrequent(vector<string>& words, int k) {
// 统计每一个单词出现的次数
unordered_map<string,int> hash;
for(auto& e : words) hash[e]++;
// 创建一个大小为k的堆
priority_queue<pair<string,int>,vector<pair<string,int>>,cmp> heap;
// 3.TopK
for(auto& e : hash)
{
heap.push(e);
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.数据流的中位数
相信大家在初中就知道中位数的求法，一堆有序的数找打中间值即可，所以我们直接来看思路。
⭐思路一：排序
这个方法我们已经替老铁们实现了，会超时，我们来看下一种写法
⭐思路二：插入的排序
这个方法我们已经替老铁们实现了，会超时，我们来看下一种写法
⭐思路三：大小堆
直接上代码：
class MedianFinder {
public:
MedianFinder() {
}
void addNum(int num) {
// 分类讨论即可
if(left.size() == right.size())
{
if(left.empty() && right.empty() || num <= left.top()) // // 左右两个堆的元素个数相同
{
left.push(num); //直接入left堆
}
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();
}
private:
priority_queue<int> left; //大根堆
priority_queue<int, vector<int>, greater<int>> right; //小根堆
};
