使用最大堆解决该问题

老师看一下这个方法行吗，效率可能低了一些，但是应该能解决问题。

包括LC.215 和求数组中的前 k 个最大元素，以下代码是求解 LC.215的 C++实现

// 使用最大堆解决该问题 C++ Version
class Solution {
 public:
  int findKthLargest(vector<int>& nums, int k) {
    priority_queue<int> pq;
    // 把数组的全部元素放入最大堆
    for (int i = 0; i < nums.size(); i++) pq.push(nums[i]);

    // 依次出队前 k 个的元素
    for (int i = 1; i <= k; i++) {
      // 返回第 k 个最大元素 (第 k 大元素)
      if (i == k) return pq.top();
      pq.pop();
    }
    return INT_MAX;
    // 如果 求前 k 个最大元素，依次出队放入数组返回即可
  }
};

我是没有昵称 2021-04-23

源自：堆，优先队列和堆排序 2-4 使用优先队列的思想解决 Leetcode 215

收起

1回答

liuyubobobo 回答被采纳获得+3积分 2021-04-23 16:21:50

可以的，思路是正确的。

但是这样做没有展现出使用优先队列方法的真正优势，即：数据可以不一次性给到，可以使用数据流的方式给出。你的写法一上来把所有元素都扔个堆，相当于要求一次性要知道所有元素。

对此，可以参考课程这一小节的分析：https://class.imooc.com/lesson/1585#mid=38640

另外，你可以尝试做一下这个问题，更能体现出使用优先队列的优势。你的这种方式就不行了：https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/

继续加油！：）

收起回答

我是没有昵称提问者 #1

感谢解答！最小堆确实是更经济合理的方式，且能处理数据流的问题，因为现实中的数据可能是不断变化的，如果我们要一直维护数据流中的前K个最大/最小元素的话，就要相应采用不同的堆来解决。以下是 LC.215 数组中的第K个最大元素用C++内置的优先队列（最小堆）的解题代码。

// 使用最小堆解决该问题
// 可以处理数据流，充分利用了最小堆的特性
class Solution {
 public:
  int findKthLargest(vector<int>& nums, int k) {
    // 使用优先队列（小顶堆/最小堆）默认是大顶堆 less<T>
    priority_queue<int, vector<int>, greater<int> > pq;

    // 把数组的前 k 个元素放入最小堆
    for (int i = 0; i < k; i++) pq.push(nums[i]);

    // 依次处理索引 >= k 后面的元素
    for (int i = k; i < nums.size(); i++) {
      // 如果当前元素大于最小堆的最小元素
      if (!pq.empty() && nums[i] > pq.top()) {
        pq.pop();      // 最小元素出队
        pq.push(nums[i]);  // 当前元素入队
      }
    }
    return pq.top();  // 当前堆顶元素即为所求
  }
};