LeetCode 703简单堆
数据流中的第 K 大元素 图解题解
这道题到底在问什么
设计一个类：构造时给定整数 k 和初始数组 nums，之后每次 add(x) 加入一个数，返回当前所有数里第 k 大的元素。本例 k=3，初始 nums=[4,5,8,2]。
- 输入
- k=3, nums=[4,5,8,2]，依次 add(3),add(5),add(10),add(9),add(4)
- 输出
- 每次 add 后报第 3 大
最优解：一步一步想明白
- 3核心一句话：维护大小 k 的最小堆，堆顶 = 第 k 大；新数 > 堆顶才挤掉堆顶。
- 4先建堆：把初始数组 [4, 5, 8, 2] 一个个加进大小为 3 的最小堆。堆是完全二叉树，画成树看更直观（堆顶在最上面）。
- 5建堆：加入 nums[0] = 4。堆里还不够 k=3 个，新数 4 直接放到堆的末尾，再上浮到正确位置。
- 6add(4) 完成。堆里还没满 3 个，暂时凑不齐第 3 大。
- 7建堆：加入 nums[1] = 5。堆里还不够 k=3 个，新数 5 直接放到堆的末尾，再上浮到正确位置。
- 85 不小于父节点 4，已经满足「父 ≤ 子」，上浮结束，位置定下来。
- 9add(5) 完成。堆里还没满 3 个，暂时凑不齐第 3 大。
- 10建堆：加入 nums[2] = 8。堆里还不够 k=3 个，新数 8 直接放到堆的末尾，再上浮到正确位置。
- 118 不小于父节点 4，已经满足「父 ≤ 子」，上浮结束，位置定下来。
- 12add(8) 完成。堆顶 4（绿色）就是当前数据流的第 3 大。堆里始终只留最大的 3 个数，最小的那个（堆顶）正是第 3 大。
- 13建堆：加入 nums[3] = 2。新数 2 还不如堆顶 4 大，进不了「最大的 3 个」，第 3 大不变，直接丢弃。
- 14add(2) 完成。堆顶 4（绿色）就是当前数据流的第 3 大。堆里始终只留最大的 3 个数，最小的那个（堆顶）正是第 3 大。
- 15数据流 add(3)。新数 3 还不如堆顶 4 大，进不了「最大的 3 个」，第 3 大不变，直接丢弃。
- 16add(3) 完成。堆顶 4（绿色）就是当前数据流的第 3 大。堆里始终只留最大的 3 个数，最小的那个（堆顶）正是第 3 大。
- 17数据流 add(5)。堆里已是目前最大的 3 个，堆顶 4 是其中最小的。新数 5 比堆顶大，说明它该进前 3 大，挤掉最小的堆顶。
- 18把堆顶替换成新数 5（紫色）。此刻它可能比孩子大，违反最小堆，需要下沉到正确位置。
- 19节点 5 已经不大于它的孩子，满足最小堆「父 ≤ 子」，下沉结束，堆顶重新成为全局最小。
- 20add(5) 完成。堆顶 5（绿色）就是当前数据流的第 3 大。堆里始终只留最大的 3 个数，最小的那个（堆顶）正是第 3 大。
- 21数据流 add(10)。堆里已是目前最大的 3 个，堆顶 5 是其中最小的。新数 10 比堆顶大，说明它该进前 3 大，挤掉最小的堆顶。
- 22把堆顶替换成新数 10（紫色）。此刻它可能比孩子大，违反最小堆，需要下沉到正确位置。
- 23堆顶 10 比孩子 5 大，违反最小堆，得把更小的 5 换上来，让大的继续往下沉。
- 24交换完成：较小的 5 回到上面。继续拿沉下去的 10 和它的孩子比，直到就位。
- 25节点 10 已经不大于它的孩子，满足最小堆「父 ≤ 子」，下沉结束，堆顶重新成为全局最小。
- 26add(10) 完成。堆顶 5（绿色）就是当前数据流的第 3 大。堆里始终只留最大的 3 个数，最小的那个（堆顶）正是第 3 大。
- 27数据流 add(9)。堆里已是目前最大的 3 个，堆顶 5 是其中最小的。新数 9 比堆顶大，说明它该进前 3 大，挤掉最小的堆顶。
- 28把堆顶替换成新数 9（紫色）。此刻它可能比孩子大，违反最小堆，需要下沉到正确位置。
- 29堆顶 9 比孩子 8 大，违反最小堆，得把更小的 8 换上来，让大的继续往下沉。
- 30交换完成：较小的 8 回到上面。继续拿沉下去的 9 和它的孩子比，直到就位。
- 31节点 9 已经不大于它的孩子，满足最小堆「父 ≤ 子」，下沉结束，堆顶重新成为全局最小。
- 32add(9) 完成。堆顶 8（绿色）就是当前数据流的第 3 大。堆里始终只留最大的 3 个数，最小的那个（堆顶）正是第 3 大。
- 33数据流 add(4)。新数 4 还不如堆顶 8 大，进不了「最大的 3 个」，第 3 大不变，直接丢弃。
- 34add(4) 完成。堆顶 8（绿色）就是当前数据流的第 3 大。堆里始终只留最大的 3 个数，最小的那个（堆顶）正是第 3 大。
- 35走完整条数据流，堆里留下的就是全程最大的 3 个数 {8, 9, 10}，堆顶 8（绿色）即最终第 3 大。全程没排序过整个数据流。
⚠️ 容易写错的地方
✗ 错：用最大堆装全部数，每次取第 k 个
✓ 对：用大小为 k 的最小堆，堆顶即答案
装全部是 O(n) 空间且取第 k 大要弹 k 次；只留 k 个最省
✗ 错：新数无脑入堆不控制大小
✓ 对：满了要先和堆顶比，比堆顶大才换
堆大小必须恒为 k，堆顶才等于第 k 大
✗ 错：把第 k 大当成第 k 个加入的数
✓ 对：是当前所有数排序后的第 k 大
与加入顺序无关，只看数值大小
完整代码（Python / C++ / Java）
Python
import heapq
class 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 大C++
class KthLargest {
priority_queue<int, vector<int>, greater<int>> h; // 小顶堆
int k;
public:
KthLargest(int k, vector<int>& nums): k(k) {
for (int x : nums) add(x);
}
int add(int val) {
if ((int)h.size() < k) h.push(val);
else if (val > h.top()) { h.pop(); h.push(val); }
return h.top(); // 堆顶 = 第 k 大
}
};Java
class KthLargest {
private PriorityQueue<Integer> h; // 小顶堆(默认最小堆)
private int k;
public KthLargest(int k, int[] nums) {
this.k = k;
h = new PriorityQueue<>();
for (int x : nums) add(x);
}
public int add(int val) {
if (h.size() < k) h.offer(val);
else if (val > h.peek()) { h.poll(); h.offer(val); }
return h.peek(); // 堆顶 = 第 k 大
}复杂度
时间
O(log k) / 次 add
一次入堆/换堆顶 = 一次 O(log k) 上浮或下沉
空间
O(k)
堆里始终只存最大的 k 个数
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 数据流中的第 K 大元素 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么不用最大堆装全部数？+
最大堆装 n 个数要 O(n) 空间，且每次查第 k 大要弹出 k 次再放回，开销大。大小为 k 的最小堆只占 O(k) 空间，堆顶 O(1) 直接读出第 k 大，单次 add 仅 O(log k)。
如果要的是第 k 小怎么办？+
对称地维护一个「大小为 k 的最大堆」，留最小的 k 个数，堆顶（这 k 个里最大的）就是第 k 小。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 数据流中的第 K 大元素 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。