215. 数组中的第 K 个最大元素

难度：🟡 Medium | 标签：堆、快速选择 | 状态：⬜ LeetCode 链接

思路

小顶堆维护当前最大的 K 个。新元素 > 堆顶时替换。最后堆顶即第 K 大。 也可快速选择 O(n) 平均，但堆解更稳。

代码

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> pq;
        for (int x : nums) {
            pq.push(x);
            if ((int)pq.size() > k) pq.pop();
        }
        return pq.top();
    }
};

复杂度

• 时间 O(n log k)，空间 O(k)
• 快选 O(n) 平均，O(n²) 最差

易错 / 回顾

• 「第 K 大」用小顶堆，「第 K 小」用大顶堆，方向反着记
• pop 在 push 之后，保证 size 恒为 k 或 k+1 临时态
• 快选要随机 pivot 防卡掉