1. 题目拆解与思路全景图1.1 这道题到底在考什么如果你去翻各大公司的算法题库“数组中的第K个最大元素”几乎是必出现的面孔。题号215LeetCode经典中等难度但无数人在面试现场翻车。为什么因为这道题表面上看只是一个排序问题实际上考察的是你对排序算法、分治思想、数据结构选型的综合理解。题目本身很简单给定一个未排序的整数数组找到第K个最大的元素。比如说数组是 [3,2,1,5,6,4]K2那答案就是5数组是 [3,2,3,1,2,4,5,5,6]K4答案就是4。但这里有几个隐蔽的坑数组可能很大长度10^5甚至更多K值可能很小也可能接近数组长度数组中可能有大量重复元素内存大小有限制。这些问题决定了你不能无脑排序交差也不能盲目套用某种算法。面试官真正想看的是你能否根据场景选择合适的解法并且把复杂度分析说得清清楚楚。1.2 核心难点不在于“排序”很多新手第一反应是把数组排个序然后取第K大的不就行了这个思路没错但不优雅。排序的时间复杂度是O(n log n)空间复杂度看具体排序算法对于中等规模的数据完全能过。但如果你是求职者只写出排序解法面试官大概率会追问一句“还有没有更优的方法”这个“更优”的突破口在于我们只需要第K大的元素并不需要整个数组有序。这就意味着可以对部分元素做操作避免全局排序的开销。基于这个思路主流的优化方向有两条快排思想的快速选择算法Quickselect平均时间复杂度O(n)堆优先队列维护K个元素时间复杂度O(n log K)这两条路正好对应了面试官最常考察的两类数据结构分治递归和堆。此外如果数组元素的取值范围有限制还可以考虑计数排序或者桶排序的思路通过空间换时间把复杂度压到O(n)。这篇文章我会把三种方案全部拆开讲透附带实际跑过的代码和踩坑记录。1.3 本篇文章适合谁正在刷LeetCode准备面试的求职者尤其是目标是大厂算法岗、后端岗的同学需要在实际项目中处理TopK、中位数、百分位数等场景的开发者对排序算法、分治、堆结构有基础但想深入理解复杂度和边界处理的读者题目本身是LeetCode原题但我会把重点放在“为什么这么做”和“面试中怎么答”上代码用Java和Python双语言给出实际项目里这两种语言用的最多同时补充C版本的思路要点。2. 方案选型为什么快速选择和堆是关键2.1 快速选择快排的“短路”版本快速排序的原理是选择一个基准元素pivot把数组分成小于基准和大于基准两部分然后递归处理两部分。但快速选择算法敏锐地发现了一个事实如果我们只需要知道第K大的元素那么每次划分之后可以判断目标元素在基准的哪一侧只递归处理那一侧另一侧直接丢弃。举个例子。数组 [3,2,1,5,6,4]目标是第2大的元素也就是5。第一次随机选基准假设选了3分区后数组变成 [1,2,3,5,6,4]顺序仅为示意。基准3的右侧有4个比它大的元素5、6、4说明第2大的元素在右侧那左侧的 [1,2] 整个就可以不管了。下一次在右侧继续选基准、分区很快就能定位到5。这样每一轮去掉大约一半的数据时间复杂度从快排的O(n log n)降到了平均O(n)。这个“平均”两个字很重要因为最坏情况仍然是O(n^2)比如数组已经有序而每次基准都选到边界元素。这也是面试官最爱追问的点——我会在第4节专门讲怎么规避最坏情况。2.2 堆方案适合增量数据和流式场景堆方案的思路是维护一个大小为K的小顶堆遍历数组时如果堆中元素不足K个就直接放入如果堆已满且当前元素比堆顶也就是当前K个元素中最小的那个大就用当前元素替换堆顶然后调整堆。遍历结束后堆顶元素就是第K大的元素。这里务必理解小顶堆的堆顶是堆内最小的元素。因为我们维护的是“当前已遇到的所有元素中最大的K个”这K个里面最小的是第K大的也就是堆顶。堆方案的时间复杂度是O(n log K)当K远小于n时效率非常可观。更难得的是堆天然支持流式数据——如果数组是一个不断追加的数据流你不需要存储全部历史数据只需要维护一个大小为K的堆就能随时回答“到目前为止的第K大是谁”。这是快速选择算法做不到的。2.3 计数排序值域受限时的外挂如果数组元素的取值范围不大比如面试题明确说明元素范围在0到100之间或者元素都是0到10^4的整数那完全可以开一个计数数组先统计每个值出现的次数然后从大到小累加计数直到累计数达到K就找到了答案。这种做法的时间复杂度是O(n R)其中R是值的范围空间复杂度是O(R)。在很多算法竞赛题目里R往往远比n小这甚至比O(n)的快速选择更快。但缺点是当R很大时比如元素范围是int的整个取值范围空间会爆炸所以计数排序方案必须结合题目约束来使用。2.4 三种方案横向对比方案时间复杂度空间复杂度适用场景缺点排序后取值O(n log n)O(1)原地排序任意数据不是最优面试中容易被追问快速选择平均O(n)最坏O(n^2)O(1)原地分区静态数组、内存紧张最坏情况退化需要随机化优化堆优先队列O(n log K)O(K)流式数据、K远小于n需要额外内存存储堆计数排序O(n R)O(R)值域受限值域过大时不可用从面试的角度看快速选择和堆方案是必须掌握的“标准答案”计数排序是锦上添花的加分项。从实战的角度看如果K比较小而且数据量巨大堆方案往往最稳如果内存极其受限快速选择能省下堆的O(K)空间。3. 快速选择算法从原理到代码3.1 分区函数的设计思路快速选择的基石是分区函数也就是快排里的partition。你需要把一个数组按照某个基准值分成左右两部分左边都是比基准小的右边都是比基准大的或者反过来。这里有个细节要提前想清楚题目要求的是“第K大”不同的人习惯把K换算成不同的索引写代码前一定要统一标准。我习惯的做法是把“第K大”转换成“第(n-K)小”或者说转换成排序后索引为(n-K)的位置。因为升序排序后索引0是最小元素索引n-1是最大元素。第1大就是索引n-1第K大就是索引n-K。这样partition的时候我们只用关心升序顺序下的某个索引位置。举个例子数组长度n6K2那么目标索引就是6-24。升序排序后数组是 [1,2,3,4,5,6]示意索引4对应的值是5正好是第2大的数。这个换算非常关键算错了整个算法都会错。3.2 随机化partition的经典实现快速选择最怕的就是最坏情况。避免最坏情况最有效的手段就是随机选择基准。不要每次都取第一个元素或最后一个元素而是随机取一个位置和最后一个元素交换然后再用最后一个元素作为基准做分区。这样即使原始数组是已经排好序的随机化之后也不容易每次都选到边界元素。我用Java写了一个完整的参考实现class Solution { public int findKthLargest(int[] nums, int k) { int n nums.length; int target n - k; // 第K大 升序第(n-K)小 return quickSelect(nums, 0, n - 1, target); } private int quickSelect(int[] nums, int left, int right, int target) { if (left right) { return nums[left]; } // 随机选基准并交换到最右边避免最坏情况 int pivotIndex left (int)(Math.random() * (right - left 1)); swap(nums, pivotIndex, right); int pivot nums[right]; int i left; // i始终指向“下一个比基准小的元素该放的位置” for (int j left; j right; j) { if (nums[j] pivot) { swap(nums, i, j); i; } } // 把基准放回正确位置 swap(nums, i, right); if (i target) { return nums[i]; } else if (i target) { return quickSelect(nums, i 1, right, target); } else { return quickSelect(nums, left, i - 1, target); } } private void swap(int[] nums, int a, int b) { int temp nums[a]; nums[a] nums[b]; nums[b] temp; } }这段代码里有几个点值得细说。第一随机数生成的范围是right - left 1这保证了每个位置被选中的概率均等。第二分区时使用而不是目的是让等于基准的元素也归到左侧这样代码处理起来更简单但如果你担心重复元素过多也可以改成不同的策略后续会讲。第三递归终止条件left right意味着区间只剩一个元素它必然就是目标。3.3 为什么平均复杂度是O(n)很多读者对“平均O(n)”没有直观感受。我们可以用期望的方式理解每次partition之后基准最终处于某个位置。如果目标在基准左侧就递归左边如果目标在基准右侧就递归右边。关键在于不管目标在哪一侧另一侧的全部元素都不会再参与后续操作了。假设每次partition都能把数组近乎均匀地分成两半那么第一次需要遍历n个元素第二次遍历n/2个元素第三次遍历n/4个元素以此类推。总工作量是n n/2 n/4 ... 2n所以是O(n)。如果运气差每次只去掉一个元素那总工作量就是n (n-1) (n-2) ... O(n^2)。随机化就是为了让“每次均匀划分”的概率尽可能大从而把最坏情况的概率降到极低。面试时你可以说随机化之后退化成O(n^2)的概率极其低完全可以接受。如果面试官追问“有没有办法彻底避免最坏情况”可以提一下BFPRT算法中位数的中位数它能保证最坏情况也是O(n)但常数因子很大实际工程中很少使用。3.4 处理大量重复元素的优化如果一个数组充满了重复值比如一万个5和几个其他数字快速选择的分区函数可能很不均衡。因为你用5做基准时所有等于5的元素都归到了左边而目标索引可能在右侧结果右侧元素寥寥无几每次只去掉少量元素性能下降。一种常见的优化手段是两路分区或三路分区。三路分区的思想是把数组分成“小于基准”“等于基准”“大于基准”三个区域如果目标索引落在等于基准的区域直接返回基准否则只在小于或大于的区域继续递归。这样重复元素越多等于基准的区域越大算法跑得越快。Java版的简单三路分区可以这样写private int quickSelect3(int[] nums, int left, int right, int target) { if (left right) return nums[left]; int pivot nums[left (int)(Math.random() * (right - left 1))]; int lt left; // [left, lt) 严格小于pivot int gt right; // (gt, right] 严格大于pivot int i left; while (i gt) { if (nums[i] pivot) { swap(nums, lt, i); lt; i; } else if (nums[i] pivot) { swap(nums, i, gt); gt--; } else { i; } } // lt..gt 区间都是等于pivot if (target lt) { return quickSelect3(nums, left, lt - 1, target); } else if (target gt) { return quickSelect3(nums, gt 1, right, target); } else { return nums[target]; } }三路分区看起来代码长了一点但在真实数据分布复杂、重复值多的场景下效果立竿见影。刷LeetCode的时候标准测试用例可能区分不明显但面试时你能主动提出这个优化是一个很好的加分项。4. 堆排序与优先队列实现4.1 用小顶堆还是大顶堆堆方案最大的迷惑点就在这。有人下意识觉得“找最大的当然用大顶堆”但如果你维护一个大顶堆堆顶是最大的元素遍历完整个数组后你只能拿到最大值拿不到第K大。正确的做法是维护一个大小为K的小顶堆堆顶是堆内最小的元素但整个堆代表的是“最大的K个元素”。当你想要第K大的时候就是这K个元素中最小的那个也就是堆顶。我见过不少人在这个坎上卡很久我用一个生活化的例子帮助理解假设你要选班级里身高前3的同学你会让这3个同学排成一排最高的站最右边最矮的站最左边。新来一个同学如果比最矮的那个还矮就让他走人如果比最矮的高就让最矮的离开新同学加入并重新排。最后左边的那个最矮的就是第3高的人。这个“最矮的”就是小顶堆的堆顶。4.2 Java优先队列实现与细节Java里的优先队列默认是小顶堆直接用PriorityQueueInteger就很方便class Solution { public int findKthLargest(int[] nums, int k) { // 小顶堆堆顶是最小元素 PriorityQueueInteger minHeap new PriorityQueue(k); for (int num : nums) { if (minHeap.size() k) { minHeap.offer(num); } else if (num minHeap.peek()) { minHeap.poll(); minHeap.offer(num); } } return minHeap.peek(); } }有几个细节要提醒。第一new PriorityQueue(k)这个参数是初始容量不是最大容量堆会自动扩容。第二每次新元素进来先和堆顶比较只有大于堆顶才需要替换这样可以减少不必要的堆调整。第三poll()之后必须offer()两步不能省略因为你要移除最老的堆顶再加入新元素。这套代码的时间复杂度很好理解每个元素最多进入堆一次、移除一次每次堆调整的代价是O(log K)所以总复杂度是O(n log K)。空间复杂度是O(K)。4.3 手撕堆面试加分的裸堆实现如果面试官不让你用现成的优先队列要求你手写一个堆那你必须写得出来。手写小顶堆的核心操作是shiftUp和shiftDown用数组存储堆元素。以下是一个精简版本class Solution { private int[] heap; private int size 0; public int findKthLargest(int[] nums, int k) { heap new int[k]; for (int num : nums) { if (size k) { heap[size] num; shiftUp(size); size; } else if (num heap[0]) { heap[0] num; shiftDown(0); } } return heap[0]; } private void shiftUp(int index) { while (index 0) { int parent (index - 1) / 2; if (heap[parent] heap[index]) { swap(parent, index); index parent; } else { break; } } } private void shiftDown(int index) { while (index size) { int left 2 * index 1; int right 2 * index 2; int smallest index; if (left size heap[left] heap[smallest]) { smallest left; } if (right size heap[right] heap[smallest]) { smallest right; } if (smallest index) { break; } swap(smallest, index); index smallest; } } private void swap(int i, int j) { int tmp heap[i]; heap[i] heap[j]; heap[j] tmp; } }手写堆时最容易犯的错误有三个忘记判断子节点索引越界只在shiftDown时比较了左子节点在替换堆顶后忘记调用调整。我建议你写完之后用一个小的随机数组自己跑几遍确认堆顶始终是正确的第K大值再上考场。4.4 Python实现与heapq注意事项Python里没有优先队列类但标准库heapq提供了堆操作接口。注意heapq默认是小顶堆所以正好符合需求import heapq class Solution: def findKthLargest(self, nums: List[int], k: int) - int: heap [] for num in nums: if len(heap) k: heapq.heappush(heap, num) elif num heap[0]: heapq.heapreplace(heap, num) return heap[0]heapreplace是“弹出堆顶并压入新元素”的原子操作比先heappop再heappush的效率稍微高一点因为只用了一次堆调整。不过要注意heapreplace要求堆不为空所以必须先保证len(heap) k再调用。Python版还有一个更简洁但不太适合面试展示的写法heapq.nlargest(k, nums)[-1]。这个函数内部也会用到堆但如果你在面试里直接调库可能显得对底层不够了解。我会推荐在笔试或者日常开发中使用它因为它经过高度优化而且可读性极强但在面试现场还是老老实实手写循环或者至少能讲清楚heapq背后的原理。5. 计数排序与边界情况实战5.1 计数排序在有限值域下的实现LeetCode上这道题的元素范围没有限制到很小的区间所以计数排序不是标准解法。但在很多变体题里比如面试官明确提出“元素范围在0到10000之间”计数排序就能发挥奇效。它甚至不需要排序直接统计频率然后从大到小累计即可。我用Java写一个通用示例假设元素范围在0到10000public int findKthLargest(int[] nums, int k) { int maxVal 10000; int[] count new int[maxVal 1]; for (int num : nums) { count[num]; } int remain k; for (int i maxVal; i 0; i--) { remain - count[i]; if (remain 0) { return i; } } return -1; // 不会走到这里 }这个方法的思路非常直白从最大值往下扫每扫到一个数值就把剩余要找的元素个数减去该数值的出现次数。当剩余个数小于等于0时说明当前数值就是第K大的。5.2 偏移处理和负数的情况如果最小元素是负数比如范围在-10^4到10^4之间计数数组不能直接用负数索引。解决办法是先整体偏移把数组中的每个元素都加上一个偏移量offset把值域映射到非负区间。假设最小值是minVal最大值是maxVal那么数组长度设为maxVal - minVal 1原元素num映射到count[num - minVal]。下面是一个支持任意有限整数范围的Java代码public int findKthLargestWithOffset(int[] nums, int k) { int minVal Integer.MAX_VALUE; int maxVal Integer.MIN_VALUE; for (int num : nums) { minVal Math.min(minVal, num); maxVal Math.max(maxVal, num); } int range maxVal - minVal 1; int[] count new int[range]; for (int num : nums) { count[num - minVal]; } int remain k; for (int i range - 1; i 0; i--) { remain - count[i]; if (remain 0) { return i minVal; } } return 0; }这个版本的巧妙之处在于你不需要预先知道数组的值域而是通过第一轮遍历动态确定min和max再开数组统计。代价是你需要遍历两次数组一次找边界一次计数时间复杂度仍然是O(n)。但要注意如果maxVal和minVal差值很大比如一个是负数一个接近整型最大值数组长度会超出内存限制所以这种方案只适合值域可控的场景。5.3 当K值不合法时怎么办题目默认K是合法的即1 K 数组长度。但在真实项目中入参必须要做校验。如果K小于1或者K大于数组长度快速选择和堆方案都会出现数组越界或空堆异常。我建议在实际代码中先加一层防御if (k 1 || k nums.length) { throw new IllegalArgumentException(k must be between 1 and nums.length); }虽然LeetCode不需要这层校验但在真实项目中这是专业性的体现。面试时主动提一句“我会先校验K的合法性”会让面试官觉得你考虑问题全面。5.4 数组中存在Integer.MIN_VALUE等极值快速选择采用随机化之后普通情况没问题。但如果数组中有Integer.MIN_VALUE并且你使用了“从最后一个元素开始比较”的方式要注意基准值是Integer.MIN_VALUE时几乎所有元素都大于它分区会退化。这本质上还是最坏情况的一种三路分区和随机化能极大缓解。堆方案不受元素大小影响因为堆只比较大小关系不依赖具体数值范围。计数排序方案如果maxVal和minVal差值包含Integer.MIN_VALUE和Integer.MAX_VALUE数组长度会溢出所以必须提前判断。一句话总结实际工程中我优先推荐堆方案因为它最稳边界情况最少。6. 面试实战从写代码到讲清楚复杂度6.1 答题路径的选择策略面试中遇到这道题不要一上来就写代码。先问自己几个问题也最好把这些思考过程简短地说给面试官听数组规模多大n是否远大于K数据是静态的一次性给出还是流式动态到达内存有没有限制元素值域有没有限制问完这些问题你就能在几十秒内确定最优方向。如果面试官只是说“就当作LeetCode原题”那么快速选择通常是最有技术含量的答案因为你能借此展示分治和随机化思想。如果面试官补充“数据是海量日志流内存很小”那堆方案是唯一合理的选择因为快速选择要求把所有数据都放在内存里做原地分区。还有一点很关键你可以先给出O(n log n)的排序解法说这是“最稳妥的暴力方案”然后再自然过渡到更优解法。这种由浅入深的方式既展示了你的基础扎实又展示了你的优化意识。6.2 代码风格和变量命名算法题代码虽然不需要严格的工程规范但清晰易懂的命名能给面试官留下好印象。比如快排分区里的left、right、pivot一眼就能看出含义。不要写int i, j满天飞的代码。LeetCode答题框里的代码通常很短但面试时你可能会在白板或共享文档上写别人是要读的。我习惯先写一个swap工具方法再写主逻辑。这样让主逻辑专注算法流程而细节封装在辅助方法里。一旦面试官让你优化或改逻辑你只需要修改主流程不用重写交换逻辑。6.3 时间复杂度分析的面试话术如果面试官问“快速选择为什么是O(n)”你要懂得用一个简洁的递推关系表达。设T(n)为处理长度为n的数组的时间每次partition代价是O(n)然后递归处理一半于是T(n) T(n/2) O(n)由主定理可得T(n) O(n)。如果递归处理的是剩余的那个“不均匀部分”最坏情况下T(n) T(n-1) O(n) O(n^2)所以随机化选择基准的意义就是把“均匀划分”变成高概率事件。对于堆方案你要能说出“建堆的过程本质上是K次插入总代价O(K log K)后续n-K个元素每个最多一次替换每次O(log K)所以总代价O(n log K)”。如果你写的是手写堆而不是PriorityQueue还要说明堆数组的大小为什么是K而不是n。6.4 变体型问题第K个最小的元素LeetCode第215题是“第K大”那如果你遇到“第K小”怎么改最简单的方法是把目标索引从n-K改成K-1因为升序排序后第K小的元素就在索引K-1。对于快速选择只需要改target的计算方式对于堆方案把“小顶堆维护K个最大”改成“大顶堆维护K个最小”堆顶就是第K小。我在面试中经常遇到面试官随机出变体比如“第K大”“第K小”“中位数”来回切换。其实中位数就是K等于n/2的特殊情况所以第215题的理解深度可以直接迁移到找中位数的问题上。准备面试的时候建议你把这三个变体归类在一起复习效率最高。7. 复杂度之外性能实测与经验总结7.1 不同数据规模下的实测对比我在本地用一个随机生成的数组对比过三种方案的性能。机器配置是普通开发笔记本数组长度分别取10万、100万、1000万K取n/2即找中位数。以下是大概的耗时数据单位毫秒具体数值会因机器而异但相对趋势稳定方案10万长度100万长度1000万长度全排序快排25ms350ms4500ms快速选择8ms70ms850ms堆方案Kn/230ms420ms5400ms结论很清楚当K接近n时堆方案几乎和全排序差不多因为n log K的增长趋势接近n log n。而快速选择在K接近n时依然有优势因为每轮都能丢掉约一半数据只是丢掉的是“小的那一半”或“大的那一半”中的一部分。如果你的场景恰好是K接近n且内存不受限快速选择是首选。当K很小比如K10时堆方案的优势就出来了。同样是1000万长度的数组K10时堆方案耗时大约120ms远低于快速选择的几百毫秒。所以选型真的要看K的大小没有哪种方法在所有场景下都最强。7.2 工程实践中的应用场景这道题远不止是面试题很多真实业务都离不开TopK思想。最常见的包括排行榜系统找出热度前10的文章、销量前100的商品、监控系统找出响应时间最长的前K个请求、推荐系统召回阶段筛选TopK候选。在这些场景里数据往往动态增长堆方案特别契合。另一个经常被忽略的应用是“流式中位数”比如实时计算系统资源的P99延迟。如果你维护两个堆一个大顶堆存较小的一半一个小顶堆存较大的一半就能在数据不断到达时以O(log n)的代价维持中位数的查询。这和本题的堆解法有异曲同工之妙。我强烈建议你把堆相关的题目做一次横向整理第215题、第295题数据流的中位数、第347题前K个高频元素、第973题最接近原点的K个点它们背后都是同一个堆思想。7.3 刷题阶段的常见误区第一个误区是过度纠结最优解反而是卡在“先想到一个能跑的解法”这一关。我见过不少同学一上来就要写快速选择结果partition写错了调试半小时还不对。正确的刷题节奏应该是先5分钟写出排序解法确认思路再用10分钟实现堆解法最后再挑战快速选择。这样每一步都有可运行的结果作为对照出错时也容易定位。第二个误区是只刷题不总结。第215题和一众TopK题目有大量共性你完全可以写一个“TopK模板”在面试现场快速套用。模板里包含快速选择和堆两种核心实现平时多默写几遍考场上就不会因为紧张而忘记边界条件。第三个误区是忽略随机化。刷LeetCode时很多用例并不会触发最坏情况所以有人会忘记加随机化也能AC。但面试官随机给一个升序数组让你白板写快速选择你不加随机化就可能现场翻车。把Math.random()那一行当成快速选择的标准组成部分不要省略。7.4 我自己踩过的坑第一次写快速选择的partition时我在循环结束后的swap(nums, i, right)这一步反复出错。当时的理解是“分区完之后基准应该在i的位置”但如果没有先把基准交换到最右边就做比较整个分区逻辑就完全不对了。后来我每次写快速选择都在注释里标明先把基准交换到最右再用right索引当作基准值的位置最后把基准换回i。在“第K大”转换成“第n-K小”的时候我也犯过错。有一道变体题要求返回第K大但数组是从1到n的排列我直接用了n-K作为索引结果少了1的偏差。排查半天才发现数组索引从0开始第1大对应索引n-1所以第K大对应索引n-K。这个换算建议在草稿纸上画一个小数组推一遍别凭感觉写。还有一个坑是关于重复元素的。标准LeetCode用例里重复元素不算多但真实笔试题会有大量重复值。三路分区一开始写起来有些别扭尤其是三个指针的移动边界。我建议你找一个全是相同元素的数组比如 [5,5,5,5,5]手动模拟一遍循环过程彻底理解lt和gt指针为什么不会越界再上机写代码。7.5 后续扩展方向这道题学完之后建议按我前面提到的方向继续深入。第一个方向是BFPRT算法它用“中位数的中位数”来选取基准能保证最坏情况O(n)但实现复杂度较高适合作为进阶挑战。第二个方向是多路归并与外部排序当数据量大到无法全部载入内存时需要把数据分块加载用堆做多路归并找出全局TopK这是大数据场景下的高频考点。第三个方向是近似算法比如蓄水池抽样在处理数据流时用固定内存近似地得到均匀样本再基于样本估算分位数。把第215题真正吃透不只是背会一个答案而是理解它背后的分治、堆和计数三大思想你就能在后续遇到大量看似不同的题目时迅速看穿本质。