题目描述#

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

思路#

第一眼看到题，咱第一反应就是——堆嘛！维护“目前为止最大的 k 个元素”，这种活儿不就是堆最擅长的吗？

具体是这么干的：开一个小顶堆，容量上限设成 k。遍历数组的时候，把每个元素都先压进堆里。一旦堆的大小超了 k，就把堆顶弹掉——因为是小顶堆，堆顶刚好是堆里最小的那个，被淘汰再合适不过。这样不变式就稳住了：堆里永远是“已经看过的元素里最大的 k 个”，而堆顶就是这 k 个里最小的，也就是当前的“第 k 大候选”。

整个数组扫完，堆里留下的就是全数组最大的 k 个元素，Peek() 取一下堆顶，正好就是答案。

代码里用的是 gods 库的 priorityqueue，比较函数写成 a - b 表示值小的优先级高、先出队，所以这是一个标准的小顶堆。这套写法时间复杂度是 O(n log k)，每次入堆出堆都是 O(log k)，空间复杂度 O(k)。

不过——题目嘴上要求的是 O(n)，本姑娘这版其实没做到严格意义上的 O(n) 哦。真要抠这一点，得换成快速选择（QuickSelect）才行。但堆的写法胜在简洁稳定，工程和面试场景都是合格答案，咱先用它顶上。

知识边界#

• 维护“前 k 大”要用小顶堆，维护“前 k 小”反过来要用大顶堆——堆顶永远是要被淘汰的那一个，方向和题目要求是反着的，这点超容易绕晕的。
• 比较函数的方向必须和堆的语义对齐：a - b 是升序、对应小顶堆；b - a 是降序、对应大顶堆。要是写反了，最后留下的就是最小的 k 个，整道题就崩啦。
• 严格 O(n) 的解法是 QuickSelect / BFPRT，思路是基于快排的 partition 只递归一边；堆解法是 O(n log k)，工程友好，但不是最优时间复杂度。

代码#

照片当然不是现实，但如果有足够多的“堆顶淘汰记录”，最后剩下的那一个，就一定是真相啦——

import (
    pq "github.com/emirpasic/gods/v2/queues/priorityqueue"
)

func findKthLargest(nums []int, k int) int {
    heap := pq.NewWith(func(a, b int) int {
        return a - b
    })
    for _, n := range nums {
        heap.Enqueue(n)
        if heap.Size() > k {
            heap.Dequeue() // 弹出最小的，保留最大的k个
        }
    }
    ans, _ := heap.Peek()
    return ans
}

好啦，这次的笔记就先到这啦——咱去整理今天的照片咯，下次再有这种坑题，本姑娘可不会再吃亏啦！