题目描述
思路解析
一句话答案：LeetCode 215 数组中第 K 个最大元素的稳妥解法是容量为 k 的小根堆：扫描数组，始终只保留目前最大的 k 个数，堆顶是这 k 个里最小的，也就是当前第 k 大；新数比堆顶大才换顶，否则丢弃。总时间 O(n log k)、空间 O(k)，k 远小于 n 时优于整体排序的 O(n log n)。
第 k 大到底指什么
题目要的是把数组降序排列后第 k 个位置上的值，重复的数照常计数，不是第 k 个不同的值。以示例 [5,2,8,1,9,3,7,4,6]、k 取 3 为例，降序前三名是 9、8、7，第 3 大就是 7。理解这一点后，问题可以重述成：从 n 个数里挑出最大的 k 个，报出其中垫底的那一个。
为什么不直接排序取第 k 个
整体排序当然能做：排完取相应下标，时间 O(n log n)。但它做了多余的工作——我们只关心最大的 k 个数是谁，排序却把全部 n 个数的相对顺序都理清楚了，k 远小于 n 时浪费明显。更要命的是排序要求一次拿到全部数据：如果数是流式一个个到来的，排序无从下手，而堆法只需要随来随处理。
求第 k 大为什么用小根堆而不是大根堆
这是全题最反直觉的一步。我们要维护的集合是「目前最大的 k 个数」，而这个集合的门槛，是它内部最小的那个元素——新数只有超过门槛，才有资格挤进来。小根堆恰好把最小值放在堆顶，门槛随手可查、可换。若改用大根堆，堆顶是 k 个里最大的，门槛沉在堆底，判断「新数该不该进」反而没法一步完成。求第 k 大配小根堆、求第 k 小配大根堆，方向记反是本题最高频的错误。
换顶规则为什么能保证答案正确
算法全程维持一条不变量：堆里装的永远是已扫过元素中最大的 k 个。新数到来分两种情况：它不大于堆顶，说明连当前门槛都过不了，绝无可能进入前 k，直接丢弃，堆不动；它比堆顶大，说明原堆顶已经保不住前 k 的席位，弹掉堆顶、放入新数、下沉调整。两种分支处理后不变量都完好，于是扫完全部 n 个数时，堆里正是全局最大的 k 个，堆顶即答案。
复杂度、快速选择与常见坑
每个数至多触发一次 O(log k) 的堆操作，总时间 O(n log k)，堆本身只占 O(k) 空间。另一条路线是快速选择（quickselect）：借快排的 partition 平均 O(n) 定位第 k 大，但最坏退化到 O(n²)，且需要全量数据在手；堆法稳定、好写、天然适配数据流场景，LC703 数据流中的第 K 大就是同一套思路的流式版。两个常见坑：把整个数组不设上限地塞进堆，复杂度退化成 O(n log n)；新数不超过堆顶时也去入堆替换，纯属无效操作还会挤错元素。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住「小根堆只留最大的 k 个，堆顶即第 k 大」，下面每来一个数都在套它。
准备 · 空堆：开局：一个空的小根堆，容量上限 3。我们要让它始终只保留「目前最大的 3 个数」，堆顶是这几个里最小的。
读 · num = 5：第 1 个数 5。堆还没满 3 个，先看看。
入堆 · 5：堆没满，直接放进堆并上浮到正确位置。现在堆里是 5，堆顶（最小）是 5。
读 · num = 2：第 2 个数 2。堆还没满 3 个，先看看。
入堆 · 2：堆没满，直接放进堆并上浮到正确位置。现在堆里是 2 5，堆顶（最小）是 2。
读 · num = 8：第 3 个数 8。堆还没满 3 个，先看看。
入堆 · 8：堆没满，直接放进堆并上浮到正确位置。现在堆里是 2 5 8，堆顶（最小）是 2。
读 · num = 1：第 4 个数 1。堆已满，拿它和堆顶（最小的 2）比一比。
丢弃 · 1：1 比堆顶 2 小（或相等）→ 它进不了「最大的 3 个」，直接丢弃。堆不变，堆顶仍是 2。
读 · num = 9：第 5 个数 9。堆已满，拿它和堆顶（最小的 2）比一比。
换顶 · 2→9：9 比堆顶 2 大 → 说明 2 不可能是最大的 3 个之一，踢掉 2、换成 9 再下沉调整。新堆 5 9 8，堆顶 5。
读 · num = 3：第 6 个数 3。堆已满，拿它和堆顶（最小的 5）比一比。
丢弃 · 3：3 比堆顶 5 小（或相等）→ 它进不了「最大的 3 个」，直接丢弃。堆不变，堆顶仍是 5。
读 · num = 7：第 7 个数 7。堆已满，拿它和堆顶（最小的 5）比一比。
换顶 · 5→7：7 比堆顶 5 大 → 说明 5 不可能是最大的 3 个之一，踢掉 5、换成 7 再下沉调整。新堆 7 9 8，堆顶 7。
读 · num = 4：第 8 个数 4。堆已满，拿它和堆顶（最小的 7）比一比。
丢弃 · 4：4 比堆顶 7 小（或相等）→ 它进不了「最大的 3 个」，直接丢弃。堆不变，堆顶仍是 7。
读 · num = 6：第 9 个数 6。堆已满，拿它和堆顶（最小的 7）比一比。
丢弃 · 6：6 比堆顶 7 小（或相等）→ 它进不了「最大的 3 个」，直接丢弃。堆不变，堆顶仍是 7。
扫描结束：扫完整个数组，小根堆里留下的正是最大的 3 个数 9、8、7，而堆顶（它们中最小的）7 就是第 3 大。答案 = 7。
边界先想清：k=1 退化成求最大值、k=n 退化成求最小值；重复值按值各占名额，逻辑都不变。
三个高频追问：堆 vs 快速选择、数据流场景、以及为什么常常不直接排序。
参考代码
import heapqdef findKthLargest(nums, k): h = [] # 小根堆 for x in nums: if len(h) < k: heapq.heappush(h, x) # 没满直接放 elif x > h[0]: heapq.heapreplace(h, x) # 比堆顶大→换顶 # 否则丢弃 return h[0] # 堆顶即第 k 大复杂度
- 时间：O(n·log k)，n 个数各做一次 O(log k) 的堆操作
- 空间：O(k)，堆里最多只装 k 个元素
易错点
面试追问把动画讲成自己的话
追问除了堆，还有别的解法吗？
追问如果是数据流（数不断来）求第 k 大呢？
追问为什么不直接排序取第 k 个？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
任务调度器
LeetCode 621 · 中等 · 沿着 堆 / 优先队列 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题