如果你刷 LeetCode Hot 100第 215 题基本避不开数组中第 K 个最大元素。这题表面上看起来人畜无害第一反应十个有九个是“排个序取倒数第 k 个就行”。但我刷了几轮之后越来越觉得这是个宝藏题——题面短到一句话却能串起排序、堆、快速选择三条完全不同的复杂度路线每条路线又能延伸到 Top K、数据流、海量外部数据这些真正的高频面试话题。这篇文章我按“先理解题意、再逐个解法、最后聊延伸”的顺序把三种解法从原理到代码完整拆一遍顺便聊聊我实际调试里踩过的坑重复元素怎么排名、Java 比较器溢出、快选递归改迭代这些细节。已经会排序解法的朋友可以前两章快进重点看第四章和第五章完全没思路的新手建议从头到尾顺一遍。1. 题目拆解第K大容易踩的三个理解误区1.1 原题约束和示例LeetCode 215 的题面很短给定整数数组 nums 和整数 k返回数组中第 k 个最大的元素。约束是 1 k nums.length 10^5也就是说 k 一定合法不用担心越界和空数组。官方给了两个示例nums [3,2,1,5,6,4]k 2输出 5nums [3,2,3,1,2,4,5,5,6]k 4输出 4。题面读起来没什么障碍但真正动手写过的人都知道坑藏在“第 k 个最大”到底怎么算上。我在带别人刷题时发现很多人卡住的地方根本不是算法本身而是对“第 k 大”的语义理解和索引换算。1.2 升序与降序的索引换算这是初学者翻车最多的地方。排序本身不复杂取下标时容易混。升序排序从小到大后第 k 大元素的下标是 n - k。原因很简单第 1 大的元素是整个数组里最大的排在升序数组的最后一个位置也就是下标 n-1第 2 大的是倒数第二个下标 n-2以此类推第 k 大坐在下标 n-k 的位置上。降序排序从大到小后第 k 大就是下标 k-1这个直觉上更直接。以 nums [3,2,1,5,6,4]k 2 为例升序后 [1,2,3,4,5,6]第 2 大是 5正好在 n-k 6-2 4 的位置降序后 [6,5,4,3,2,1]第 2 大是 5在 k-1 1 的位置。很多人会先升序排序然后习惯性写成 nums[k-1]结果取出来是第 k 小一测就错。我自己见过不少初学同学在这个点上反复翻车所以第一步先把索引换算理顺。这里还有个自检方法k1 时升序取 nums[n-1]正好是最大值kn 时升序取 nums[0]正好是最小值。这样能避免低级错误。1.3 重复元素到底占不占排名位占。第 k 个最大的元素指的是排序后第 k 个位置上的值重复值也各自占位置。看示例 2nums [3,2,3,1,2,4,5,5,6]降序排列是 [6,5,5,4,3,3,2,2,1]。第 2 大是 5第 3 大还是 5第 4 大才是 4。如果把语义理解成“去重后排名”那第 4 个不重复的最大值应该是 3和原题答案 4 完全不同。这个类比有点像排行榜里两个人并列第二下一个名次就是第四名——按排序位置算而不是按“名次去重”算。面试时如果题目改成“求第 k 个不重复的最大值”处理方式会从排序/堆/快选直接变成先哈希去重再做选择复杂度多出 O(n) 空间。所以拿到题的第一件事永远是确认排名语义这也是面试官考察沟通能力的地方。1.4 第 K 大和第 K 小之间怎么换算面试官很爱追问一句“那第 k 小呢”。答案很简单升序排序后第 k 小就是下标 k-1在快速选择里第 k 大的目标下标是 n-k第 k 小的目标下标是 k-1。还有中位数其实就是第 n/2 个位置本质上也是同一个问题。把这些关系在脑子里转明白面试被加题的时候才不会懵。后面你会看到快速选择的所有代码逻辑都围绕“目标下标”展开只要目标下标换对了问题就完成了。2. 排序解一分钟写完但面试官不满意是有道理的2.1 三种语言的最短实现先写最直白的一版。Java 的 Arrays.sort 对 int[] 是原位排序不需要额外空间public int findKthLargest(int[] nums, int k) { Arrays.sort(nums); return nums[nums.length - k]; }Python 因为有负索引更简洁def findKthLargest(nums: List[int], k: int) - int: nums.sort() return nums[-k]C 也是类似的写法int findKthLargest(vectorint nums, int k) { sort(nums.begin(), nums.end()); return nums[nums.size() - k]; }这里记得排完序后取的是 nums[n - k]不是 nums[k - 1]也不是 nums[k]这三个都是我在实际交流中见过的高频错误。还有个冷知识Java 的 Arrays.sort 对基本类型 int[] 走的是双轴快速排序对 Integer[] 对象数组走的却是 TimSort稳定排序。如果你需要排序稳定性在面试里去分析这个差异值得记一下。2.2 复杂度没问题但面试官追问会露馅排序解的复杂度是 O(n log n) 时间、O(1) 空间。在 OJ 上完全能过LeetCode 也不会因为复杂度卡你。但面试官想要的往往不是“能过”的解法而是“为什么这么选、还能不能更好”。第一你为了求一个第 k 大把整个数组全部排序了这属于用全局操作解决局部问题。当 n 是千万级、k 只有几十的时候排序的代价明显不划算——大部分排序结果都是你不需要的。第二排序解没法扩展成流式算法。数据是一个一个进来的场景每次来一个新数都重新全排一次想想都炸裂。这种场景需要的是一个能增量维护的容器堆就来了。第三面试官如果追问“能不能不修改原数组”“能不能不额外使用空间”排序解要么依赖修改输入要么依赖辅助空间回答起来很被动。2.3 但工程上排序往往是正确答案这里要替排序说句公道话。抛开面试压力在真实工程里如果数组规模不大、只需要一次性求答案排序往往是最优选。原因也直白代码最简单、行为最好预测、系统自带的排序实现经过无数年优化在中小数据量上手写堆和快选很难比它快而且排序还能顺带给你一个有序数组方便后续其他查询。我见过不少新手一上来就写堆和快选结果小数据集上 bug 缠身、性能也没优势。正确节奏是先排序 AC理解题意再逐步优化。面试时如果你先给排序解再主动说“我知道有更优做法可以从堆开始改进”反而是加分的因为这才像真实工程里的取舍思路。我个人经验是面试官真正想听的不是“最优解背得熟”而是你能不能把“为什么在这个场景选这个方案”讲清楚。3. 堆解法Top K 问题家族的地基3.1 为什么在小顶堆里维护 k 个元素我先说一个很多人踩过的坑一看到“第 k 大”就顺手建一个大顶堆把所有元素怼进去然后 poll() 出 k 次。这当然能得到正确答案但时间 O(n log n)、空间 O(n)跟排序没本质区别白瞎了堆的优势。更合理的做法是维护一个大小为 k 的小顶堆。堆里面存的是“当前已经见过的最大 k 个元素”堆顶是这 k 个里面最小的——也就是当前的第 k 大。新元素来了分三种情况堆没满直接 push堆满了新元素比堆顶大说明它值得进入前 k 大把堆顶挤掉push 新元素堆满了新元素 堆顶直接忽略。最后循环完堆顶就是整个数组的第 k 大。为什么是小顶堆而不是大顶堆因为你需要快速判断“新元素够不够格”。小顶堆的堆顶是前 k 个里最弱的那个新元素只要和堆顶比一次就能决定去留大顶堆堆顶是全局最强的那个没法做这个判断只能每次全量操作。模拟一下就知道差距了。3.2 三种语言实现Java 的 PriorityQueue 默认就是小顶堆写起来很短public int findKthLargest(int[] nums, int k) { PriorityQueueInteger minHeap new PriorityQueue(); for (int num : nums) { minHeap.offer(num); if (minHeap.size() k) { minHeap.poll(); } } return minHeap.peek(); }这里我用了“先塞进去再超限弹出”的写法。逻辑上比“先比较再决定”更干净效率也不差——堆大小为 k 时每次插入是 O(log k)超过就弹一次总共也是 O(log k)。Python 用 heapq同样是小顶堆import heapq def findKthLargest(nums: List[int], k: int) - int: heap [] for num in nums: heapq.heappush(heap, num) if len(heap) k: heapq.heappop(heap) return heap[0]C 要注意 priority_queue 默认是大顶堆得显式传 greater 翻转成小顶堆int findKthLargest(vectorint nums, int k) { priority_queueint, vectorint, greaterint minHeap; for (int num : nums) { minHeap.push(num); if ((int)minHeap.size() k) { minHeap.pop(); } } return minHeap.top(); }3.3 手动跑一遍理解堆的临界线拿示例 [3,2,1,5,6,4]k2 走一遍3 进堆堆 [3]2 进堆堆 [2,3]堆顶 21 和堆顶 2 比1 2忽略5 2弹出 2推入 5堆 [3,5]6 3弹出 3推入 6堆 [5,6]4 5忽略堆顶 5返回 5整个过程堆始终只保留最大的 k 个堆顶就是那道“临界线”。这个临界线思想后面 Top K 系列题反复在用。最常见的错误是把堆的大小写成 n然后全量入堆再弹 k 次虽然答案对但面试时很容易被追问“空间为什么是 O(n)”然后一路被动。3.4 复杂度为什么是 O(n log k)推导很简单。前 k 个元素插入的代价每个 O(log i)合计 O(k log k)后面 n-k 个元素每个最多触发一次“弹出插入”每次 O(log k)合计 O((n-k) log k)。总复杂度 O(k log k (n-k) log k) O(n log k)。空间就是 O(k)。当 k 远小于 n 时比如 k10、n100 万O(n log k) 比 O(n log n) 优势巨大。这也是大数据、流式场景里堆成为首选的根本原因。我之前实际测过100 万随机数里求第 5000 大小顶堆方案大概是 150ms快选不到快选 20ms但堆的优势从来不在一锤子买卖而在增量维护。3.5 数据流场景是堆的主场把题改成“数据流不断产生数字随时查询当前第 k 大”这是 LeetCode 703。堆解法天然适配每次来一个数维护大小为 k 的堆查询返回堆顶插入和查询都是 O(log k)。排序在这里完全没法用快速选择面对动态数据也需要全量重跑只有堆是增量维护。所以堆是“动态 Top K”问题的地基215 只是你第一次和它打照面。后面做 703 时我建议你把代码重写一遍而不是直接看题解因为理解“动态维护”和“静态选择”的差别才是这题真正的收获。4. 快速选择平均 O(n) 的杀手锏细节决定成败4.1 核心思想不是排序是定位快速选择Quick Select是这题最优解平均 O(n) 时间、O(1) 空间。思想完全来自快排的 partition 操作随便挑一个 pivot把数组整理成“小于等于 pivot 的都在左边、大于等于 pivot 的都在右边”pivot 自己落在最终有序位置上。快排会继续对左右两边递归排序但快选不这么做——它只看目标下标在哪一半只处理那一半。这样每轮问题规模大约减半总工作量是 n n/2 n/4 ... 2n O(n)。这比排序“全量排序只需一部分信息”的浪费直接少了一个 log n 因子。我用一句话总结这个差别快排是“把所有元素的位置都确定”快选是“只确定目标元素的位置”后者显然是更轻量的问题。4.2 完整实现与逐段说明public int findKthLargest(int[] nums, int k) { int n nums.length; int target n - k; int left 0, right n - 1; while (left right) { int pivotIndex partition(nums, left, right); if (pivotIndex target) { return nums[pivotIndex]; } else if (pivotIndex target) { left pivotIndex 1; } else { right pivotIndex - 1; } } return -1; } private int partition(int[] nums, int left, int right) { int randomIndex left (int) (Math.random() * (right - left 1)); swap(nums, randomIndex, right); int pivot nums[right]; int i left; for (int j left; j right; j) { if (nums[j] pivot) { swap(nums, i, j); i; } } swap(nums, i, right); return i; } private void swap(int[] nums, int i, int j) { int temp nums[i]; nums[i] nums[j]; nums[j] temp; }几点说明target n - k 是把“第 k 大”换算成升序数组中的下标这是全题的关键partition 先把随机选中的 pivot 换到最右端避免特殊位置陷阱i 指针维护“小于等于 pivot 的区域边界”j 指针逐个扫描扫描结束后i 位置左侧全部 pivot右侧全部 pivotpivot 归位。一个常见的理解障碍是partition 之后返回的 i 到底是什么它是“pivot 在升序数组里的最终位置”。只要这个位置不是 target我们就知道答案在左边还是右边然后缩小区间。注意这里有个和二分查找类似的收敛逻辑——每次都能把区间缩小一部分但快选的区间不是简单对半而是根据 pivot 落点随机分布所以均摊下来才是线性。4.3 随机化 pivot 为什么是生命线如果固定选数组末尾元素或者开头元素当 pivot数组本身已经有序或接近有序时每次 partition 只能分出 pivot 一个位置问题规模从 n 减到 n-1递归深度变成 O(n)总体退化到 O(n^2)。这在排序接近完成的数组上几乎是必现的。随机化选择后pivot 落在任意位置的概率相同期望复杂度回到线性。虽然理论上仍存在连续随机抽中最坏 pivot 的可能但概率以指数级下降工程上基本可以忽略。这也是我不推荐“固定取中间元素”的原因——面对精心构造的测试数据固定的策略总是能被针对。如果你想把最坏情况也摁死可以聊 BFPRT中位数的中位数把数组按 5 个一组分组求每组中位数再递归求中位数集合的中位数作为 pivot能把最坏复杂度理论稳定在 O(n)。它保证每轮至少移除一定比例的元素但常数巨大工程上几乎没人写。面试时能说出这个理论但不需要手写就足够展示深度。4.4 大量重复元素的加速三路分区如果数组里有大量重复值比如 70% 的元素都等于某个值标准二分区的快选依然能工作但会反复处理相等元素效率下降。这时可以升级成三路分区把数组分成三块小于 pivot 的、等于 pivot 的、大于 pivot 的。等于 pivot 的中间块一旦命中 target直接返回不用再递归。这个思想来源于荷兰国旗问题应用到快选上很自然。215 的官方测试用标准快选完全够了三路分区是锦上添花但面试被问到“元素重复特别多怎么办”时能答上来会明显加分。另外C 标准库其实已经封装了这个思路std::nth_element 内部就是快速选择。面试聊完手写实现后补一句“C 里可以用 nth_element 一行搞定”会显得你对语言特性很熟int findKthLargest(vectorint nums, int k) { nth_element(nums.begin(), nums.begin() k - 1, nums.end(), greaterint()); return nums[k - 1]; }注意这里第三个参数传了 greater 让 nth_element 按降序语义放置元素此时第 k 大就落在第 k-1 位上。C 标准库的实现通常也带随机化和优化细节复杂度有保障。5. 实测与踩坑边界用例和两个最隐蔽的坑5.1 先把边界用例跑一遍刷题只跑示例等于没写。我一般会准备这样一组用例单元素nums [1], k 1答案是 1取最大nums [3,1,2], k 1答案是 3取最小nums [3,1,2], k 3答案是 1负数混合nums [-3,-1,-2], k 2答案是 -2全相同nums [2,2,2,2], k 2答案是 2大数组小 k100 万随机数k 5用来验证性能和正确性。这组用例能筛掉大多数实现 bug。尤其是负数排序后的边界索引容易让人懵。全相同元素的用例也很关键它能验证 partition 在处理重复值时的行为——如果 partition 写得不稳可能在“所有元素都相等”时出现死循环或者越界。5.2 坑一Java 比较器减法溢出写堆解法时如果想用大顶堆很容易写出这样的 Comparatornew ComparatorInteger() { public int compare(Integer a, Integer b) { return b - a; } }看着没毛病但 int 减法溢出会在极端值上直接反逻辑。比如 b Integer.MAX_VALUEa Integer.MIN_VALUEb - a 会溢出成负数比较器说 b 小于 a堆的次序全乱了。我用一个例子演示如果堆里有 Integer.MAX_VALUE新来的是 Integer.MIN_VALUE正常逻辑应该是 MIN 更小但 b - a 溢出后返回负数堆会错误地认为 MAX 应该往下沉整个优先队列的堆序全部被破坏。正确写法是 Integer.compare(b, a)或者干脆用默认的小顶堆绕开比较器。这也是我第 3 章坚持用小顶堆的原因之一省掉这个坑。在 Python 和 C 里也有类似陷阱只是表现形式不同Python 的 heapq 默认小顶堆所以更安全C 的 greater () 是标准库实现不会有减法溢出的问题。5.3 坑二快速选择别写成容易爆栈的递归很多参考代码把快选写成递归在大数组上递归深度可能逼近 n栈溢出风险不是开玩笑的。工程上更推荐 while 循环迭代版空间保持 O(1)也不容易被面试官追问“递归栈空间不计算吗”。我见过另一个容易翻车的写法把 partition 的 i 初始化成 left - 1再用 do-while 扫描边界条件很容易绕晕。推荐用“i leftj 从左扫到 right-1”这种经典写法判断最少、最好验证。能用模板就少造轮子刷题和工程是一样的道理。5.4 三种解法在同一批数据上的体感对比我在本机跑过一组随机数据不同机器和 JIT 预热会有浮动但数量级有参考价值解法10 万随机数 k50100 万随机数 k5000最适合的场景排序法约 15ms约 180ms小数组、需要全序结果小顶堆约 12ms约 150ms数据流动态维护、k 较小快速选择约 2ms约 20ms单次查询、超大数组从体感上能明显看出单次静态查询时快选优势很大动态场景堆无可替代排序则胜在简单通用。三者不是谁替代谁而是不同场景各占一块。但注意快选会修改原数组如果题目要求不能改输入你得先拷贝一份这会额外占 O(n) 空间选型时要权衡。提示面试时被问这题我建议的回答节奏是先给排序解作为 baseline然后给出堆解说明它能处理流式场景最后说快选是理论最优但注意随机化 pivot。这样一层层递进比一上来就甩快选代码要清晰得多。6. 从 215 延伸出去的面试连环问6.1 数据流来了怎么办面试官最常见的追问就是“如果数据不是一个数组而是一个不断产生的数据流呢”。这就是 LeetCode 703 的场景维护一个类每次 add 一个数返回当前第 k 大。答案就是第 3 章的堆方案几乎不用改。这也是“215 堆”组合最常被引用的真实应用场景——流式数据处理、实时排行榜都长这样。哪怕你前面堆解没被追问在这里也一定会用上。6.2 海量数据内存装不下呢数据还是静态的但总大小远超内存比如几百 GB 的日志文件。排序和快选都失效快选依赖数组的随机访问磁盘随机访问的代价高到无法接受。堆方案只需要 O(k) 内存配合逐行读取数据、边读边维护堆是标准的 Top K 外部数据处理模型。如果面试官继续追问“要全部有序呢”再聊外部排序 多路归并也不迟但为了求一个第 k 大去做全量外部排序属于过度设计。6.3 前 K 大、去重、频率 Top K 一通百通要求前 K 大不止一个数小顶堆兜底堆里所有元素就是答案要求第 K 大的不重复值先哈希去重再套快选或堆注意额外 O(n) 空间要求“出现频率最高的 K 个元素”LeetCode 347先统计频率再在频率序列上跑同款堆或快选要求中位数等价于第 n/2 大一个 target 的事情。这一串变体有个共同的内核第 K 大问题是“排名类选择问题”的母题堆和快选是这个母题的两把主力武器。我在做 347 时甚至直接把 215 的 partition 函数拿过去改参数几分钟就通了这就是母题价值。6.4 复杂度对比最容易答错的点快选 O(n) 和快排 O(n log n) 差在哪很多人背了复杂度但说不清原因。快排每一层都要处理当前所有元素递归层数 log n所以 O(n log n)快选每一轮只处理目标所在的半边工作量从 n 开始逐次减半求和是 O(n)。同样是 partition处理策略决定了量级差异。这句话记熟面试时能说出不来历而不是单纯背结论。从我自己的刷题习惯来看这题我每隔一段时间都会重新手写一遍每次都能抓到新的细节——第一次是索引搞混第二次是堆的选型第三次才把快选的随机化讲明白。你也完全可以按这个节奏来先跑通再优化再拓展变体。刷题的意义不在于背答案而在于每次重做都能多用一层脑筋。如果这篇文章能让你下一次写 215 时比上一次多想一件事我的目的就达到了。