#215
中等
高频
min-heap数组中的第K个最大元素
这是一道围绕数组、分治、快速选择展开的高频练习。建议先掌握「min-heap」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。
数组
分治
快速选择
排序
堆
题目分析
给你一个无序数组和一个整数 k，要求返回数组里第 k 个最大的元素。
这里的“第 k 个最大”是按排序后的排名来算，不是去重之后的第 k 个不同元素。
比如 [3,2,1,5,6,4] 里，第 2 个最大元素就是 5。
一句话概括：
不用把整个数组排好序，只需要找出排完序后第 k 个最大的位置是谁。
接下来怎么看推荐代码： 带着这个理解再看推荐代码时，重点观察这条主线：用大小为
k 的小顶堆维护当前见过的最大 k 个元素，堆顶就是第 k 大。推荐代码
推荐解法：min-heap
时间复杂度： O(n log k)
空间复杂度： O(k)
核心思路： 用大小为
k 的小顶堆维护当前见过的最大 k 个元素，堆顶就是第 k 大。
class Solution {
public int findKthLargest(int[] nums, int k) {
// 创建小顶堆，维护k个最大元素
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : nums) {
if (minHeap.size() < k) {
// 堆未满，直接添加
minHeap.offer(num);
} else {
// 堆已满，比较堆顶
if (num > minHeap.peek()) {
// 当前元素大于堆顶，替换堆顶
minHeap.poll();
minHeap.offer(num);
}
}
}
// 堆顶即为第k大元素
return minHeap.peek();
}
}
结构化讲解
面试时怎么讲
开场思路
这题我会用大小固定为 k 的小顶堆，而不是先把整个数组完全排序。
核心过程
- 遍历数组，把每个元素都放进小顶堆。
- 如果堆大小超过
k，就弹出最小值，保证堆里只保留最大的k个元素。 - 这样遍历结束后，堆顶就是这
k个元素里最小的那个。 - 这个值正好就是整个数组的第
k大元素。
复杂度总结
时间复杂度 O(n log k)，空间复杂度 O(k)。
面试补一句：这题最重要的不变量是“堆里永远只留最大的 k 个数”。
核心思路
第 K 大元素不需要把整个数组完全排好序。只要一直保留最大的 k 个数，最后这批数里最小的那个，就是答案。
步骤讲解
1
维护一个大小为 k 的小顶堆
遍历数组时，把元素放进小顶堆，让堆里始终保存当前最大的 k 个元素。
为什么这样做：小顶堆堆顶正好代表这
k 个元素里最小的那个，也就是当前第 k 大。对应代码提示：PriorityQueue heap = new PriorityQueue<>();
2
新元素入堆后及时裁剪
每加入一个元素，如果堆大小超过 k，就弹出堆顶最小值。
为什么这样做：这样可以把不可能成为第
k 大的较小元素及时淘汰掉。对应代码提示：if (heap.size() > k) heap.poll();
3
遍历结束后读取堆顶
扫描结束时，堆中剩下的正好是最大的 k 个数，堆顶即答案。
为什么这样做：第
k 大的定义就是“最大的 k 个数中最小的那个”。对应代码提示：return heap.peek();
易错点
用了大顶堆却没控制大小
这样虽然也能得到排序效果，但空间会变成 O(n)，且不必要。
正确理解：优先使用大小固定为
k 的小顶堆。把“第 k 大”写成下标排序问题
如果直接完整排序，虽然能做，但没有利用题目只要一个位置值的特点。
正确理解：抓住“只保留最大 k 个”这个更小的问题规模。
堆大小超出 k 后没及时弹出
这样堆顶就不再代表第 k 大，整个不变量会失效。
正确理解：每次入堆后都立即判断
size > k 并 poll()。复杂度与适用判断
时间复杂度：O(n log k)
空间复杂度：O(k)
比其他方案更好在哪里：比完整排序的
O(n log n) 更有针对性，尤其适合 k 远小于 n 的场景。适用判断：题目只关心 Top K 或第 K 大/小，而不要求完整排序时，优先想到堆。
额外提醒
- 固定堆大小，是这题空间和逻辑都成立的关键。
动画演示
如果你还没完全看懂，可以展开动画演示。
min-heap动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
min-heap动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
准备就绪 - 点击开始按钮查看小顶堆动画
动画演示仅在桌面端提供，移动端请优先阅读推荐代码与结构化讲解。