LC.215「数组中的第K个最大元素」大厂面试出镜率TOP5。你当然可以Arrays.sort()然后取下标O(nlogn) 能过但面试官会追问“如果n 10⁹内存放不下整个数组怎么办”“如果数据是流式到达的不能回头你怎么办”这时候堆才是正确答案。今天我们用容量k的小顶堆以O(nlogk)时间、O(k)空间解决这个问题——而且堆的底层数组实现的完全二叉树我们一并讲透让你面试时既能写API也能手撕底层。 题目速览30 秒读懂给定数组nums和整数k返回数组中第k个最大的元素。示例[3,2,1,5,6,4], k2 → 输出5示例[3,2,3,1,2,4,5,5,6], k4 → 输出4重复元素各占名次约束n ≤ 1e5数值范围±1e4。全局排序能过但面试官期待更优解。 核心思路用“最鸡肋的元素”做看门狗暴力思路先排序再取nums[n-k]O(nlogn)。能过但面试官会问“如果n10⁹呢”堆的直觉——为什么是“小顶堆”我们要找的是第k大等价于保留最大的k个数其中最小的那个就是第k大。维护一个容量为k的小顶堆堆里存的是当前见过的“最大的k个数”堆顶是这k个数里最小的也就是最“鸡肋”的遍历每个数如果堆没满 → 直接入堆如果x 堆顶→ 踢掉堆顶它不配留在前k大让 x 入堆如果x ≤ 堆顶→ x连前k大的门槛都够不着直接扔掉遍历结束堆顶就是答案。为什么不用大顶堆大顶堆取最大值容易但容量如果设为k你永远不知道该踢谁——因为你不知道当前最大值是否属于最终的前k大。小顶堆的设计让“最该被踢的”恰好暴露在堆顶。️ 图解算法手把手走一遍nums [3,2,1,5,6,4],k2维护容量2的小顶堆步骤当前元素堆内容堆顶在前动作13[3]堆未满入堆22[2, 3]堆未满入堆后 2 上浮到顶31[2, 3]1 堆顶 2直接扔掉45[3, 5]5 堆顶 2弹出 25 入堆上浮56[5, 6]6 堆顶 3弹出 36 入堆64[5, 6]4 堆顶 5直接扔掉遍历结束堆 {5, 6}堆顶5就是第2大✅️ 堆的底层藏在数组里的完全二叉树堆是一棵完全二叉树用数组存储节点i的左孩子2*i 1节点i的右孩子2*i 2节点i的父节点(i-1)//2两个核心操作上浮sift_up新元素加在数组末尾和父节点比较比父小小顶堆就交换直到合适位置。下沉sift_down堆顶被替换后和孩子中较小的比较大了就交换直到合适位置。建堆为什么是O(n)而不是O(nlogn)自底向上从最后一个非叶节点开始下沉约一半节点是叶子不用动约1/4节点最多下沉1层1/8下沉2层……求和收敛于O(n)。直觉便宜的节点多贵的节点少摊下来线性。 代码实现Python手写堆 Java PriorityQueuePython版手写堆面试必备classSolution:deffindKthLargest(self,nums:List[int],k:int)-int:heap[]# 小顶堆defsift_up(i):whilei0:p(i-1)//2ifheap[i]heap[p]:heap[i],heap[p]heap[p],heap[i]ipelse:breakdefsift_down(i,size):while2*i1size:child2*i1ifchild1sizeandheap[child1]heap[child]:child1# 选较小的孩子ifheap[i]heap[child]:heap[i],heap[child]heap[child],heap[i]ichildelse:breakforxinnums:iflen(heap)k:heap.append(x)sift_up(len(heap)-1)elifxheap[0]:heap[0]x sift_down(0,k)returnheap[0]Java版PriorityQueue工程写法classSolution{publicintfindKthLargest(int[]nums,intk){// 小顶堆容量 kPriorityQueueIntegerheapnewPriorityQueue();for(intx:nums){heap.offer(x);if(heap.size()k){heap.poll();// 自动弹出堆顶最小值}}returnheap.peek();}}⚠️防坑提醒Python的heapq默认是小顶堆如果要大顶堆要push-x。Java的PriorityQueue默认小顶堆用Comparator.reverseOrder()变成大顶堆。手写堆时sift_down的循环条件是2*i1 size不是别搞混。⏱️ 复杂度分析面试必问维度堆解法全局排序时间O(nlogk)O(nlogn)空间O(k)O(1)原地排序或O(n)复制当k远小于n时比如k10n1e6堆解法几乎线性而全局排序要处理百万级数据。当数据流式到达时堆更是唯一选择。 举一反三3 道高频变种题题目变化点应对策略LC.347 前K个高频元素按频率找Top-K哈希表统计频率堆存(频率, 元素)依然是容量k的小顶堆LC.23 合并K个升序链表多路归并堆存K个链表头每次弹最小值并推入其后继LC.295 数据流的中位数动态找中位数一个大顶堆存较小一半 一个小顶堆存较大一半保持堆大小平衡 面试追问模拟提前准备Q1为什么第k大要用“小顶堆”而不是大顶堆小顶堆的堆顶是堆里最小的正好是我们想随时“踢掉”的那个。每来一个新数比堆顶大就踢掉堆顶换新人保证堆里始终是“最大的k个数”。如果用大顶堆你无法判断该踢谁。Q2建堆为什么是O(n)能不能一句话讲清楚自底向上建堆时高度为h的节点数量约n/2(h1)下沉代价为h总代价Σh·n/2(h1) O(n)。便宜的节点多贵的高层节点少摊下来线性。Q3Java的PriorityQueue底层是什么线程安全吗底层是动态数组实现的二叉小顶堆offer/poll是O(logn)peek是O(1)。不是线程安全的并发场景用PriorityBlockingQueue。Q4如果数据是流式到达不能一次性拿到全部堆解法还能用吗完全能用。流式场景下堆解法是黄金标准——每个元素来的时候直接处理不需要存储历史数据。这正是它相比“全局排序”的最大优势。 实战小技巧刷题党必备口诀第k大小顶堆容量k堆顶就是它。模板凡是“流式Top-K”、“海量数据找最大/最小K 个”优先堆。防溢出Java中用Comparator.reverseOrder()实现大顶堆不要手写(a,b)-b-a可能溢出。 实际应用场景不止是刷题任务调度器操作系统按优先级调度进程PriorityQueueDijkstra最短路径每次取距离最近的未访问节点堆优化大数据Top-K统计海量日志中找访问量最高的IP延迟队列按时间戳排序处理到期任务 今日思考题如果题目要求找“第k小”堆应该怎么改提示用容量k的大顶堆保留最小的k个数堆顶就是第k小。如果找“前k大”但要求输出排序后的结果堆还能做到吗复杂度是多少