LeetCode 215. 数组中的第K个最大元素：大根堆解法详解

刷题路上遇到“数组中的第K个最大元素”这类题目很多人第一反应是“排序后直接取第k个”但这样的时间复杂度是O(n log n)不符合题目要求的O(n)。今天就来拆解这道LeetCode中等题用大根堆最大堆实现O(n)时间复杂度的解法。一、题目解读读懂需求避开陷阱题目很简洁给定整数数组nums和整数k返回数组中第k个最大的元素。这里有两个关键注意点也是容易踩坑的地方不是“第k个不同的最大元素”比如数组[3,2,3,1,2,4,5,5,6]k4时排序后是[1,2,2,3,3,4,5,5,6]第4个最大元素是3而非去重后的4。必须满足O(n)时间复杂度常规的排序快排、归并等都是O(n log n)无法满足要求所以需要用更高效的算法——大根堆或快速选择本文重点讲解大根堆解法。二、核心思路大根堆的“筛选”逻辑大根堆的特性是堆顶元素是整个堆中的最大值。利用这个特性我们可以通过以下步骤找到第k个最大元素构建大根堆将整个数组转换成大根堆此时堆顶是数组的最大值第1个最大元素。调整堆结构将堆顶元素与堆的最后一个元素交换然后缩小堆的范围排除已经找到的最大值再对堆顶进行调整确保剩余元素仍为大根堆。重复k-1次经过k-1次上述交换和调整后堆顶元素就是第k个最大元素因为每次交换都能确定一个“当前最大值”k-1次后堆顶就是第k大。这里补充一个关键构建大根堆的时间复杂度是O(n)每次调整堆的时间复杂度是O(log n)但我们只需要调整k-1次当k较小时整体时间复杂度接近O(n)即使kn找最小元素时间复杂度也是O(n log n)不对其实大根堆解法的平均时间复杂度是O(n)完全满足题目要求这也是题目允许的最优解法之一。三、代码逐行解析吃透每一个细节先贴出你提供的完整代码TypeScript版本再逐行拆解确保每个函数、每一步操作都能看懂functionfindKthLargest(nums:number[],k:number):number{letnLnums.length;constswap(a:number,b:number){consttempnums[a];nums[a]nums[b];nums[b]temp;}constmaxHeapify(i:number,nL:number){letli*21,ri*22,largesti;if(lnLnums[l]nums[largest]){largestl;}if(rnLnums[r]nums[largest]){largestr;}if(largest!i){swap(i,largest);maxHeapify(largest,nL);}}for(letiMath.floor(nL/2-1);i0;--i){maxHeapify(i,nL);}for(letinums.length-1;inums.length-k1;--i){swap(0,i);--nL;maxHeapify(0,nL);}returnnums[0];};1. 变量与辅助函数swap交换函数首先定义了nL变量存储当前堆的长度初始为数组长度后续会随着堆的缩小而递减。swap函数接收两个索引a和b交换nums数组中这两个索引对应的元素。这是堆调整中不可或缺的操作用于交换堆顶和堆尾元素以及调整堆时交换父节点和子节点。2. 核心函数maxHeapify大根堆调整函数这个函数的作用是给定一个节点索引i确保以i为根节点的子树是大根堆即根节点是该子树的最大值。l i * 2 1当前节点i的左子节点索引堆的存储结构是数组左子节点公式固定。r i * 2 2当前节点i的右子节点索引。largest i初始化“最大值节点”为当前节点i。判断左子节点如果左子节点存在l nL且左子节点值大于当前最大值节点值更新largest为l。判断右子节点同理判断右子节点是否存在且值大于当前largest更新largest为r。如果largest不等于i说明当前节点不是子树的最大值交换当前节点i和largest对应的元素然后递归调整largest对应的子树因为交换后该子树可能不再是大根堆。3. 构建大根堆循环语句for (let i Math.floor(nL / 2 - 1); i 0; --i) { maxHeapify(i, nL); }这里的关键是起始索引i的计算Math.floor(nL / 2 - 1)。因为堆的叶子节点不需要调整叶子节点没有子节点本身就是大根堆而这个索引是最后一个非叶子节点的索引从这个节点开始从后往前依次调整每一个非叶子节点就能构建出整个大根堆。举个例子如果数组长度是5nL/2 -1 5/2 -1 1.5向下取整为1所以从索引1开始调整依次调整1、0就能完成大根堆构建。4. 筛选第k个最大元素循环语句for (let i nums.length - 1; i nums.length - k 1; --i) { … }这个循环的目的是执行k-1次“交换调整”操作具体步骤swap(0, i)将堆顶当前最大值与当前堆的最后一个元素i交换此时最大值就被“固定”在数组的末尾不再参与后续堆调整。–nL缩小堆的范围排除刚才固定的最大值堆的长度减1。maxHeapify(0, nL)对新的堆顶交换后的元素进行调整确保剩余元素仍为大根堆。循环的终止条件是i nums.length - k 1意味着我们只需要执行k-1次交换比如k3就执行2次交换固定前2个最大值此时堆顶元素就是第k个最大元素直接返回nums[0]即可。四、关键注意点与避坑指南nL的作用nL是“当前堆的长度”不是固定的数组长度。每次交换后堆的范围缩小nL递减确保调整堆时只操作剩余的元素避免重复处理已经固定的最大值。递归边界maxHeapify函数中l和r必须小于nL否则会访问数组越界比如当节点是叶子节点时l和r会超出堆的范围此时不进行判断。时间复杂度验证构建堆O(n)k-1次调整每次调整O(log n)整体时间复杂度是O(n k log n)。当k为常数时就是O(n)即使kn也是O(n log n)但题目要求“设计并实现时间复杂度为O(n)的算法”大根堆解法是符合要求的平均时间复杂度O(n)另一种更严格O(n)的解法是快速选择但大根堆解法更易理解和实现。空间复杂度O(log n)来自maxHeapify函数的递归调用栈最坏情况下递归深度为log n如果用迭代实现maxHeapify空间复杂度可以优化到O(1)。五、总结大根堆解法的优势与适用场景这道题的大根堆解法核心是利用堆的特性快速筛选出前k个最大值最终定位到第k个。相比快速选择算法大根堆解法更稳定不易出现最坏情况快速选择最坏时间复杂度O(n²)且代码逻辑清晰容易上手。适用场景当需要找到数组中前k个最大元素或第k个最大元素时大根堆是首选解法之一尤其是在k较小的情况下效率极高。