题目描述
思路解析动画文字版
核心一句话：维护大小 k 的最小堆，堆顶 = 第 k 大；新数 > 堆顶才挤掉堆顶。
先建堆：把初始数组 [4, 5, 8, 2] 一个个加进大小为 3 的最小堆。堆是完全二叉树，画成树看更直观（堆顶在最上面）。
建堆：加入 nums[0] = 4。堆里还不够 k=3 个，新数 4 直接放到堆的末尾，再上浮到正确位置。
add(4) 完成。堆里还没满 3 个，暂时凑不齐第 3 大。
建堆：加入 nums[1] = 5。堆里还不够 k=3 个，新数 5 直接放到堆的末尾，再上浮到正确位置。
5 不小于父节点 4，已经满足「父 ≤ 子」，上浮结束，位置定下来。
add(5) 完成。堆里还没满 3 个，暂时凑不齐第 3 大。
建堆：加入 nums[2] = 8。堆里还不够 k=3 个，新数 8 直接放到堆的末尾，再上浮到正确位置。
8 不小于父节点 4，已经满足「父 ≤ 子」，上浮结束，位置定下来。
add(8) 完成。堆顶 4（绿色）就是当前数据流的第 3 大。堆里始终只留最大的 3 个数，最小的那个（堆顶）正是第 3 大。
建堆：加入 nums[3] = 2。新数 2 还不如堆顶 4 大，进不了「最大的 3 个」，第 3 大不变，直接丢弃。
add(2) 完成。堆顶 4（绿色）就是当前数据流的第 3 大。堆里始终只留最大的 3 个数，最小的那个（堆顶）正是第 3 大。
数据流 add(3)。新数 3 还不如堆顶 4 大，进不了「最大的 3 个」，第 3 大不变，直接丢弃。
add(3) 完成。堆顶 4（绿色）就是当前数据流的第 3 大。堆里始终只留最大的 3 个数，最小的那个（堆顶）正是第 3 大。
数据流 add(5)。堆里已是目前最大的 3 个，堆顶 4 是其中最小的。新数 5 比堆顶大，说明它该进前 3 大，挤掉最小的堆顶。
把堆顶替换成新数 5（紫色）。此刻它可能比孩子大，违反最小堆，需要下沉到正确位置。
节点 5 已经不大于它的孩子，满足最小堆「父 ≤ 子」，下沉结束，堆顶重新成为全局最小。
add(5) 完成。堆顶 5（绿色）就是当前数据流的第 3 大。堆里始终只留最大的 3 个数，最小的那个（堆顶）正是第 3 大。
数据流 add(10)。堆里已是目前最大的 3 个，堆顶 5 是其中最小的。新数 10 比堆顶大，说明它该进前 3 大，挤掉最小的堆顶。
把堆顶替换成新数 10（紫色）。此刻它可能比孩子大，违反最小堆，需要下沉到正确位置。
堆顶 10 比孩子 5 大，违反最小堆，得把更小的 5 换上来，让大的继续往下沉。
交换完成：较小的 5 回到上面。继续拿沉下去的 10 和它的孩子比，直到就位。
节点 10 已经不大于它的孩子，满足最小堆「父 ≤ 子」，下沉结束，堆顶重新成为全局最小。
add(10) 完成。堆顶 5（绿色）就是当前数据流的第 3 大。堆里始终只留最大的 3 个数，最小的那个（堆顶）正是第 3 大。
数据流 add(9)。堆里已是目前最大的 3 个，堆顶 5 是其中最小的。新数 9 比堆顶大，说明它该进前 3 大，挤掉最小的堆顶。
把堆顶替换成新数 9（紫色）。此刻它可能比孩子大，违反最小堆，需要下沉到正确位置。
堆顶 9 比孩子 8 大，违反最小堆，得把更小的 8 换上来，让大的继续往下沉。
交换完成：较小的 8 回到上面。继续拿沉下去的 9 和它的孩子比，直到就位。
节点 9 已经不大于它的孩子，满足最小堆「父 ≤ 子」，下沉结束，堆顶重新成为全局最小。
add(9) 完成。堆顶 8（绿色）就是当前数据流的第 3 大。堆里始终只留最大的 3 个数，最小的那个（堆顶）正是第 3 大。
数据流 add(4)。新数 4 还不如堆顶 8 大，进不了「最大的 3 个」，第 3 大不变，直接丢弃。
add(4) 完成。堆顶 8（绿色）就是当前数据流的第 3 大。堆里始终只留最大的 3 个数，最小的那个（堆顶）正是第 3 大。
走完整条数据流，堆里留下的就是全程最大的 3 个数 {8, 9, 10}，堆顶 8（绿色）即最终第 3 大。全程没排序过整个数据流。
边界都围绕「堆是否满」和「新数和堆顶的大小」两件事。
两个高频追问：空间/时间优势、对称求第 k 小。
参考代码
import heapqclass KthLargest: def __init__(self, k, nums): self.k = k self.h = nums[:] # 最小堆 heapq.heapify(self.h) while len(self.h) > k: # 只留最大的 k 个 heapq.heappop(self.h) def add(self, val): if len(self.h) < self.k: heapq.heappush(self.h, val) elif val > self.h[0]: # 比堆顶大才挤掉堆顶 heapq.heapreplace(self.h, val) return self.h[0] # 堆顶 = 第 k 大复杂度
- 时间：O(log k) / 次 add，一次入堆/换堆顶 = 一次 O(log k) 上浮或下沉
- 空间：O(k)，堆里始终只存最大的 k 个数
易错点
面试追问把动画讲成自己的话
追问为什么不用最大堆装全部数？
追问如果要的是第 k 小怎么办？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最后一块石头的重量
LeetCode 1046 · 简单 · 沿着 堆 / 优先队列 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题