1. 这道题到底在考什么top-K问题的本质与题眼我最早接触“7-1 寻找大富翁”这道题是在PTA的数据结构题单里题目本身不长第一行给出N和M第二行给出N个整数代表每个人的资产要求输出资产最高的前M位。初看就是个排序题很多人第一反应是“排个序、取前M个、完事”但真上了考场或者做大N用例就会发现问题没那么简单——N可以非常大M却相对小直接把N个数据全部排序时间和空间的消耗都有点奢侈。这道题在数据结构课程里的定位其实是一个典型的Top-K问题。Top-K问题在算法面试和工程实践里出现频率极高排行榜取前100名、日志系统里统计出现次数最多的IP、电商平台筛选价格最贵的商品本质上都是同一类问题。而“寻找大富翁”妙就妙在它把Top-K问题包装成了一个人畜无害的排序题让没想清楚的人用最笨的办法也能过掉一部分测试点然后在大数据点上露出破绽。1.1 从题目描述到问题本质先把题目抽象一下。“寻找大富翁”的输入约束通常是N可以到10的5次方甚至10的6次方M一般不超过100。这就意味着在绝大多数用例里M远小于N甚至可以说M和N不是一个数量级。那我们真正要回答的问题就变成了在N个数里怎么高效地找出最大的M个数并且按降序输出。这里的核心矛盾是高效率和大数据量之间的矛盾。如果把问题简化成“从N个数里找最大的数”大家都知道只需要扫一遍O(N)就能解决。如果简化成“找前两个最大的数”呢很多人就习惯性地先排序再取前两个但实际只要一遍扫描维护两个变量就能搞定。那么“前M个最大的数”呢其实思路可以延续用一个容量为M的容器遍历整个数组始终保持这个容器里存放的是“目前为止最大的M个数”遍历结束后容器里的就是答案。顺着这个思路走这道题就不再是普通的排序题了。排序的复杂度是O(N log N)而“维护容器”的思路可以做到O(N log M)。当M远小于N时两者差距非常明显。1.2 关键题眼N分钟级超大M却小得可怜为什么说M远小于N是这个题的题眼我举个例子假设N 10^6M 10。如果用快速排序做全排序比较次数大约是10^6 × 20 ≈ 2×10^7这在单组数据下可以接受但不能忽视的是内存要存下10^6个整数也就是大约4MB的数组如果金额用int存这其实也还好。但题目如果进一步放大到N 10^7甚至10^8或者你在工程场景里面对的文件数据根本装不进内存那“全排序再取前M”的路线就直接宣告死亡。更合理的做法是数据边读边处理内存里只保留M个元素最终只返回M个数。这其实就是这道题最有价值的地方——它逼着你去思考“我们真的需要把N个数全排好吗”答案当然是否定的。你要的只是前M个大的剩下的N-M个数是死是活、顺序如何跟你毫无关系。搞清楚这一点就等于找到了这个题真正的题眼不完整排序也叫部分排序。2. 先别急着排序三种解法的复杂度和适用场景对比在PTA上做这道题你至少有三条路可以走。三条路都能过但在不同数据范围下性价比完全不同。我建议你不要只满足于会一种最好把三种都写一遍因为每种解法背后的思想在以后的工作里都会遇到。2.1 解法A全排序——最直观但最浪费最容易想到的解法读入N个数用快速排序或堆排把整个数组按降序或升序排好然后输出前M个。在C语言里直接用stdlib.h里的qsort就能搞定。如果是Csort就更加顺手。#include stdio.h #include stdlib.h int cmp(const void *a, const void *b) { return *(int *)b - *(int *)a; // 降序 } int main() { int n, m; scanf(%d %d, n, m); int *a (int *)malloc(sizeof(int) * n); for (int i 0; i n; i) { scanf(%d, a[i]); } qsort(a, n, sizeof(int), cmp); for (int i 0; i m i n; i) { if (i) printf( ); printf(%d, a[i]); } printf(\n); free(a); return 0; }这段代码能拿多少分碰到N比较小、时间限制宽松的用例直接满分通过。但它的时间复杂度是O(N log N)空间复杂度是O(N)。当N上到10^6甚至更高时全排序的规模就有点吓人了而且一旦题目加大N到内存装不下的程度这个方案在工程上根本不可行。我在实际测试里发现PTA的数据如果N10^5、M100快排和后面讲的堆解法在时间上几乎看不出差别都是十几毫秒。只有到N10^6以上差距才开始显现。这也是为什么很多人在考场上用qsort也能AC就觉得这题没什么含金量——其实只是测试数据没有卡到那个份上。2.2 解法B部分选择排序——M很小时的反直觉赢家第二种思路是只做部分排序。外层循环跑M趟每一趟在剩余的序列里找出最大值放到前面。这样只用排最大的M个位置剩下的不管。#include stdio.h int main() { int n, m; int a[1000005]; scanf(%d %d, n, m); for (int i 0; i n; i) { scanf(%d, a[i]); } if (m n) m n; for (int i 0; i m; i) { int maxIdx i; for (int j i 1; j n; j) { if (a[j] a[maxIdx]) { maxIdx j; } } if (maxIdx ! i) { int temp a[maxIdx]; a[maxIdx] a[i]; a[i] temp; } } for (int i 0; i m; i) { if (i) printf( ); printf(%d, a[i]); } printf(\n); return 0; }这段代码的复杂度是O(N×M)。什么情况下划得来当M非常小比如M1或者M10的时候它比全排序快得多。N10^6、M10的时候扫描次数是10^7比快排的约2×10^7还低一些而且它不需要递归常数更小。但这个方法有个隐患如果M稍微变大比如M1000复杂度就是10^9直接超时没商量。所以我把它称为“反直觉赢家”——在M极小极小的场景里它很猛但适用范围很窄。你在PTA上如果直接用这个提交会因为M100恰好也能过而觉得自己找到了正解其实在数据范围更大的题库里它就很危险。2.3 解法C小顶堆——应对海量数据的正规军第三种解法是经典的小顶堆方案也是我觉得这道题真正的“标准答案”。核心思想维护一个容量为M的小顶堆堆顶是堆里最小的元素。遍历N个数如果堆没满当前堆大小小于M直接把数插入堆中如果堆满了比较当前数和堆顶如果当前数比堆顶大说明堆里那个最小的元素该被淘汰了用当前数替换堆顶然后下沉调整如果当前数小于等于堆顶直接丢弃。遍历结束后堆里剩下的M个数就是最大的M个数最后把它们从堆里取出来按降序输出。这个方案的时间复杂度是O(N log M)空间复杂度是O(M)。最大的优势是不需要一次性把N个数全部载入内存可以边读边处理。这在工程上的意义非常大——假设N是一个文件里的上亿行数据你不可能全部塞进内存但堆只需要M个元素的存储轻轻松松就能在流式场景下工作。2.4 三种解法的复杂度和实测对比我拿几组典型数据在本地跑过这里给出一张直观的对比表方案时间复杂度空间复杂度N10^5, M100N10^6, M100工程可用性全排序快排O(N log N)O(N)极快较慢数据必须全量在内存部分选择排序O(N×M)O(N)较快约10^8次比较勉强大M场景直接退化小顶堆O(N log M)O(M)极快极快支持流式数据实测中N10^6、M100的时候全排序大概需要几十毫秒堆解法只需要不到一半的时间而且内存只用了400字节的堆空间加上少量临时变量远小于4MB的数组。数据量越大这种差距越悬殊。所以说如果你只是想在PTA上拿分用全排序没问题但如果你想通过这道题真正理解Top-K问题的解法小顶堆才是最值得掌握的方案。3. 堆解法的每一个细节从小顶堆的构建到最终排序输出堆解法听起来高大上但当你把代码写出来会发现核心操作其实就两个上浮sift_up和下沉sift_down。这两个操作搞明白堆的插入和替换就都解决了。3.1 为什么是小顶堆而不是大顶堆这是一个我一开始就想反了的点。正常人看到“找最大的M个数”第一反应是建一个大顶堆然后把N个数全部塞进去最后从堆顶依次弹出M个。这个思路对不对对但很低效。因为大顶堆里存的是N个数你只是在用堆排序的壳做了一次全排序复杂度O(N log N)空间O(N)没有任何优势。小顶堆的思路完全相反堆里只存M个数而且堆顶是这M个数里的最小值。每来一个新的候选数只需要跟堆顶比较——如果新数比堆顶小直接不要如果比堆顶大说明它更有资格留在“暂定Top-M”里于是把堆顶替换掉。这样一来遍历完所有数堆里留下来的正是最大的M个数。这个“暂定Top-M”的说法很关键。你维护的堆永远是一个“暂时的排行榜”随着数据的流入排行榜的门槛也就是堆顶不断被抬高最终剩下的就是真正的Top-M。3.2 堆操作拆解上浮、下沉与淘汰逻辑用数组实现堆下标从0开始。对节点i它的左孩子是2×i1右孩子是2×i2父节点是(i-1)/2。上浮操作用于插入新元素把元素放到堆尾然后不断和父节点比较如果比父节点小就交换直到满足小顶堆性质。下沉操作用于替换堆顶后的调整把堆顶和左右孩子里较小的那个比较如果比孩子大就交换然后继续向下调整。关键的区别在于上浮在插入时发生下沉在堆顶被替换时发生。我在代码里把这两个操作都写出来方便对比。3.3 完整C代码与核心细节注释下面给出一份可以直接在PTA上提交的C语言完整代码#include stdio.h int heap[105]; // 容量为M的小顶堆M不会太大 int heapSize 0; // 当前堆中元素个数 int n, m; void swap(int *a, int *b) { int t *a; *a *b; *b t; } // 下沉从节点i开始向下调整小顶堆 void siftDown(int i) { int l 2 * i 1; int r 2 * i 2; int smallest i; if (l heapSize heap[l] heap[smallest]) { smallest l; } if (r heapSize heap[r] heap[smallest]) { smallest r; } if (smallest ! i) { swap(heap[i], heap[smallest]); siftDown(smallest); } } // 上浮从节点i开始向上调整小顶堆 void siftUp(int i) { int parent (i - 1) / 2; while (i 0 heap[parent] heap[i]) { swap(heap[i], heap[parent]); i parent; parent (i - 1) / 2; } } // 检查并插入一个数 void insertNum(int x) { if (heapSize m) { // 堆未满直接插入堆尾并上浮 heap[heapSize] x; siftUp(heapSize); heapSize; } else if (x heap[0]) { // 堆满了如果新数大于堆顶当前最小的一个替换并下沉 heap[0] x; siftDown(0); } } int main() { scanf(%d %d, n, m); if (m n) m n; // 处理 MN 的情况最多只能输出 N 个 for (int i 0; i n; i) { int x; scanf(%d, x); insertNum(x); } // 堆排序从小到大把堆元素取出来再反着输出 int res[105]; int originalSize heapSize; for (int i 0; i originalSize; i) { res[i] heap[0]; // 取出当前堆顶最小元素 heap[0] heap[heapSize - 1]; heapSize--; siftDown(0); } for (int i originalSize - 1; i 0; i--) { if (i ! originalSize - 1) printf( ); printf(%d, res[i]); } printf(\n); return 0; }这里我刻意把“取出来排序”这步也写完整了。因为堆里存的虽然是最小的在堆顶但我们最终要降序输出所以先把堆里的元素从小到大一个个取出来存到res数组里然后逆序输出。这其实就是一个简版的堆排序。有人会问为什么不能在堆内部直接降序因为在数组实现的堆里想要输出有序序列最方便的办法就是反复取堆顶、删除堆顶而每次取出来的都是当前堆里最小的所以结果自然是升序逆序一下就是我们要的降序。从代码里还能看到一个小小的处理如果M大于N直接把M改成N。这是因为输入给的M可能比实际人数还多你总不能让人数不够还硬输出更多吧。这个边界在题目里不一定明说但测试数据里很可能会有一组N3、M5的用例一不留神就数组越界。4. 容易白给分的边界条件与输出格式坑越是简单的题越容易在奇奇怪怪的地方失分。这道题我见过太多人挂在同样的地方每次都是测试点一片红不是算法不行而是边界和格式没处理好。4.1 M和N的边界关系N小于等于M怎么办第一种边界情况也是最常被忽略的就是M比N还大。题目说“输出前M位大富翁”但N个人总共就N位哪来M位可输出正确做法是输出全部N个数按降序。有的同学直接写for (int i 0; i m; i)当MN时数组就越界了。你如果开数组开得大一点倒不会崩但会输出一堆垃圾数据或者是跑到循环外总之结果错得莫名其妙。我从一开始就在堆解法里加了if (m n) m n;这个操作放在读入之前或者读入之后都可以。它的作用是保证整个程序接下来都按照“有效人数”为M去处理无论是堆的容量还是最后的输出个数都统一了省得后面每个循环都要判断。4.2 输出格式最后一个空格引发的“爆零”PTA的判题系统对输出格式非常严格。要求每个数字之间用一个空格分隔但行末不能有多余空格。换句话说1 2 3是合法的1 2 3末尾多一个空格很可能会被判定为格式错误Presentation Error这在PTA上通常算错。怎么避免通用的写法是“第一个数前面不加空格后面的数前面加一个空格”也就是我在代码里写的for (int i 0; i m; i) { if (i) printf( ); printf(%d, a[i]); } printf(\n);这段逻辑只判断“是不是第一个”不判断“是不是最后一个”写起来最安全也不容易漏。还有一种写法是先输出第一个再循环输出后面的但那样要单独处理m为0的情况虽然本题中M应该是正整数但稳妥起见还是用统一写法最好。4.3 大数据量下scanf才是王道这道题的N可以到10^5甚至更大输入量不小。很多从Python或者C切过来的同学习惯用cin读数据但在PTA的数据结构课程题里用C语言的scanf通常是最稳的选择。这段经验是我自己踩坑换来的N10^6时用cin且不关同步的话读入就要花好几秒直接超时换成scanf之后只需要零点几秒。C里如果一定要用cin记得加ios::sync_with_stdio(false);关掉和stdio的同步不然性能差距巨大。你要是用纯C写就不用纠结这个直接scanf一把梭。如果金额可能是长整数把int换成long long读取格式改成%lld就行。这个细节题目里不一定写清楚但看数据范围基本能猜出来。4.4 数值相等的用例会带来哪种“隐藏坑”最后一类隐藏坑是数值相等的情况。比如N5M3资产是100 90 90 80 70输出应该是100 90 90。这个用例对堆解法来说没有任何问题因为当新数等于堆顶时我们走的是x heap[0]这个分支的else也就是直接丢弃不会把相等的数换进去。如果题目要求“如果并列也输出且名次占位”之类的规则那处理就要变但本题只是输出前M大的值所以重复值直接跳过完全没问题。真正会出问题的是有人为了追求“稳定排序”而在相等时也做替换白白增加不必要的调整次数虽然结果一样但效率变差了。记住相等的时候直接扔不要换。这既符合业务逻辑又省时间。5. 从PTA走向真实场景大数据Top-K问题还能怎么玩说实话这道题之所以能成为数据结构题单里的常客不是因为堆这个知识点本身有多难而是因为它背后的Top-K思想在真实工程里太常用了。我自己在做日志分析、排行榜系统的时候就多次用到同样的套路只不过真实场景中会有更多约束。5.1 只能遍历一次的数据流场景想象一个场景你有一个超级大的日志文件里面记录了上亿条用户访问数据内存装不下而且数据是源源不断流入的。你想实时知道“目前访问次数最高的K个用户是谁”怎么做这个时候你不可能把所有用户和访问次数都存下来再排序因为内存不够。正确做法就是维护一个小顶堆每个用户的访问次数更新后和堆顶比一下如果比堆顶大就替换。这个堆的容量只有K无论数据量多大内存占用始终是常数级别。我当初就是先做了PTA这道题后来在实习的时候遇到类似需求脑海里立刻浮现出“用小顶堆卡住Top-K”的思路几乎是一比一复刻。这也是为什么很多公司面试爱考Top-K——它确实是从课本到工业界的一道桥梁。5.2 快速选择算法与堆的取舍除了堆Top-K问题还有另一个很有名的解法快速选择Quickselect。它基于快速排序的分治思想每轮确定一个pivot的最终位置然后决定去左边还是右边递归查找。对比维度小顶堆快速选择时间复杂度O(N log K)平均O(N)最坏O(N²)空间需求O(K)O(N)数据必须全量在内存是否支持流式支持边读边处理必须全量读入稳定性稳定但不保序不稳定工程适用场景海量数据、流式、内存受限数据可全量装入内存、追求常数更低从这个表能看出来堆的普适性更强快速选择在数据量可控时更快。PTA这道题因为可能存在内存限制和流式读取的需求更推荐堆解法。5.3 分布式Top-K的一种朴素思路再往外延伸一步真实系统里数据量大到单机处理不了的时候Top-K问题就变成了分布式问题。朴素思路是“分而治之”把数据切分成多份分别分发给多台机器每台机器用堆算出自己那份数据的Top-K最后把各台机器的K个结果汇总再做一次Top-K筛选。这个思路在MapReduce框架里非常常见map阶段各自统计reduce阶段做全局归并。这个思想背后的原理还是“每个分区先缩小候选集”。因为全局Top-K一定在某个分区的Top-K里这是显然成立的——如果某个分区里某个数连该分区的Top-K都进不了那它在全局更不可能排到Top-K前面。把这个直觉想明白你对Top-K问题的理解就又深了一截。做这道题的时候我第一次感到“数据结构题原来真的能用在工程里”以前学堆觉得就是考试用直到在真实场景里面对“上亿行数据找Top100”的需求时才发现教科书里的每一样东西都是有用武之地的。如果非要说一个做这道题最值得记住的点我会选这个当你发现自己准备把海量数据全部排序只为了取一点点最大值时停下来想想是不是有一个容量只有M的容器就够了。这个思维转换比AC这道题本身更有价值。