【优先级队列】最后一块石头的重量 && 数据流中的第 K 大元素
【优先级队列】最后一块石头的重量 && 数据流中的第 K 大元素
1046. 最后一块石头的重量
有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
- 如果
x == y，那么两块石头都会被完全粉碎； - 如果
x != y，那么重量为x的石头将会完全粉碎，而重量为y的石头新重量为y-x。
最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。
示例：
输入：[2,7,4,1,8,1]
输出：1
解释：
先选出 7 和 8，得到 1，所以数组转换为 [2,4,1,1,1]，
再选出 2 和 4，得到 2，所以数组转换为 [2,1,1,1]，
接着是 2 和 1，得到 1，所以数组转换为 [1,1,1]，
最后选出 1 和 1，得到 0，最终数组转换为 [1]，这就是最后剩下那块石头的重量。提示：
1 <= stones.length <= 301 <= stones[i] <= 1000
解题思路：优先级队列
对于每次要选取最大值或者最小值的问题，几乎都可以采用优先级队列来解决，只不过要注意的是选择的是大根堆还是小根堆，选对了才能正确的解决问题！这道题要选的是最重的石头，也就是最大的数值，那么我们就需要一个大根堆！
然后每次在大根堆中取堆顶的两个元素进行比较，注意此时第一个堆顶元素应该是 y 才对，因为这是大根堆，然后第二个堆顶元素是 x，然后判断 x 是否小于 y，是的话将其差值添加到堆中即可！
循环上述操作，最后堆顶元素就是结果，只不过需要判断特殊情况，因为有可能最后两个石头完全粉碎，那么堆中没有元素，要返回 0，所以需要特判一下，并不难！
class Solution {
public:
int lastStoneWeight(vector<int>& stones) {
// 先将元素都放入优先级队列中
priority_queue<int> pq;
for(int i = 0; i < stones.size(); ++i)
pq.push(stones[i]);
// 然后每次取堆顶两个元素进行比较
while(pq.size() > 1)
{
int y = pq.top();
pq.pop();
int x = pq.top();
pq.pop();
if(x < y)
pq.push(y - x);
}
return pq.empty() ? 0 : pq.top();
}
};703. 数据流中的第 K 大元素
设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。
请实现 KthLargest 类：
KthLargest(int k, int[] nums)使用整数k和整数流nums初始化对象。int add(int val)将val插入数据流nums后，返回当前数据流中第k大的元素。
示例：
输入：
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
输出：
[null, 4, 5, 5, 8, 8]
解释：
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3); // return 4
kthLargest.add(5); // return 5
kthLargest.add(10); // return 5
kthLargest.add(9); // return 8
kthLargest.add(4); // return 8提示：
1 <= k <= 1040 <= nums.length <= 104-104 <= nums[i] <= 104-104 <= val <= 104- 最多调用
add方法104次 - 题目数据保证，在查找第
k大元素时，数组中至少有k个元素
解题思路：优先级队列
这也是一道经典的 TOPK 问题，其实有两种做法，第一就是用 优先级队列，时间复杂度为 O(nlogk)，第二就是之前学过的 快速选择算法，时间复杂度可以近似为 O(n)，但是时间复杂度也就是 O(n)，这在海量数据处理中是接受不了的，所以一般解决这种问题我们还是使用优先级队列，但是第二种快速选择算法我们也要掌握！
因为这道题要求的是第 k 大的元素，所以我们要用 小根堆。
不过这道题还是有些细节的，如果我们每次调用 add 函数的时候再去创建一个小根堆去进行 topk 处理的话，是需要重新遍历数组元素的，在这道题的测试用例中是会超时的，所以我们需要做点小优化！
我们可以将优先级队列作为成员变量，然后在构造函数中先处理完传入的 nums 数组中的元素，先将数据入堆，然后判断当堆元素达到 k 个之后，则将堆顶那个小的 pop 掉即可，那么之前入堆的小的元素就被弹出去了，一直就能保持堆中元素不大于 k 个！
然后每次在调用 add 的时候，只需要处理传入的 val 即可，就不需要每次重新处理一次数组中的元素了！
class KthLargest {
private:
int _k;
priority_queue<int, vector<int>, greater<int>> _heap; // 创建一个小根堆
public:
KthLargest(int k, vector<int>& nums) {
_k = k;
// 将数据入堆
for(int i = 0; i < nums.size(); ++i)
{
_heap.push(nums[i]);
// 注意当堆元素达到k个之后，则将堆顶那个小的pop掉即可
if(_heap.size() > _k)
_heap.pop();
}
}
int add(int val) {
// 将val加到堆中去
_heap.push(val);
// 然后将堆顶那个小的pop掉即可，最后堆顶就是第k大的数
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);
*/腾讯云开发者
