★ FEATURED ARTICLE 这道题看起来是在找谁最安静真正难的是这么多人有前后关系先算谁、后算谁就成了关键。顺序排对了答案才能一路往下传而且不用反复回头算。这篇就从这个顺序入手看看这道题为什么要这么排以及为什么这样算一定对。先把它想成一家公司为了讲得顺后面把题目里的人看成同一家公司的员工安静值就当成每个人的安静指数。规则一个字没改只是换了个叫法。题目给的信息就是谁比谁有钱。每个人都有一个安静指数数字越小越安静。对每个员工要做的都是同一件事在他自己以及所有比他有钱的人里面挑出最安静的那个人。答案就是那个人的编号。这里有个容易漏掉的地方比他有钱是会滚雪球的。A 比 B 有钱B 比 C 有钱那 A 也算比 C 有钱哪怕 A 和 C 之间没有直接写关系。题目保证这种关系不会绕成一个圈比如不会出现 A 比 B 有钱、B 又比 A 有钱这种情况。这就是题目说的逻辑自洽。最笨的做法对每个人顺着关系网把所有比他有钱的人都捞出来再挑一个最安静的。关系网翻来覆去走好几遍人一多操作次数就要成倍往上翻。慢的原因在于重复同一个上级的信息被他下面每一层都重新捞了一遍。这种重复没有带来任何新东西。换个方向没有上级的人先算关键的一句话没有上级的人先算完。这样的人候选名单里只有他自己答案铁定就是他本人。他算完就通知那些直接比他穷的下级我这边的答案是 X。你把 X 跟你手上现在的答案比一比谁更安静就留谁。收到通知的人把自己还欠几个直接上级的通知这个计数减一。减到 0说明他的上级全都算完了答案也就定下来了可以接着通知下级。这个计数就叫欠账是整道题的开关。还有上级没通知他他的答案就还可能变。欠账清零该给他的答案就都到齐了。走一遍例子取一组小数据走一遍quiet [3, 2, 5, 4] 编号 0、1、2、3安静指数分别是 3、2、5、4 richer [[0,1], [1,2], [3,2]]三组关系读出来是0 比 1 有钱1 比 2 有钱3 比 2 有钱。画成图箭头从有钱的指向没钱的0 → 1 → 2 3 ──────→ 2先看哪些人没有上级。没人比 0 有钱也没有人比 3 有钱所以这两个人可以先算。答案先全部设成自己ans [0, 1, 2, 3]处理 0他的答案就是 0安静指数 3。通知下级 1手上答案ans[1] 1 安静指数 2 新来的 ans[0] 0 安静指数 3安静指数 2 比 3 小所以不换。1 的欠账减到 01 算完了。处理 3答案就是 3安静指数 4。通知下级 2手上答案ans[2] 2 安静指数 5 新来的 ans[3] 3 安静指数 4安静指数 4 比 5 小换。ans[2]从 2 改成 3。2 的欠账从 2 减到 1还欠一个因为 1 还没通知他。处理 1答案在前面就定下来了就是 1安静指数 2。通知下级 2手上答案ans[2] 3 安静指数 4 新来的 ans[1] 1 安静指数 2安静指数 2 更小换。ans[2]改成 1。2 的欠账减到 02 也算完了。结果ans [0, 1, 1, 3]。核对一遍人候选名单自己加上所有比他有钱的最安静的00011、01安静指数 222、1、3、01安静指数 2333对上了。翻译成 Java 代码classSolution{publicint[]loudAndRich(int[][]richer,int[]quiet){intnquiet.length;// 建图箭头从有钱的指向没钱的ArrayListArrayListIntegergraphnewArrayList();for(inti0;in;i){graph.add(newArrayList());}// indegree[i] 还有几个人直接比 i 有钱也就是 i 还欠几个通知int[]indegreenewint[n];for(int[]r:richer){graph.get(r[0]).add(r[1]);// r[0] 比 r[1] 更有钱连边 r[0] → r[1]indegree[r[1]];// r[1] 多欠一个上级}// 数组加两个指针当队列用int[]queuenewint[n];intl0;// 队头intr0;// 队尾// 没人比他有钱的人先入队他们不欠任何上级for(inti0;in;i){if(indegree[i]0){queue[r]i;}}// 答案先全部设成自己int[]ansnewint[n];for(inti0;in;i){ans[i]i;}while(lr){intcurqueue[l];for(intnext:graph.get(cur)){// cur 比 next 有钱所以 cur 的答案也是 next 的合法候选// 谁更安静就留谁数字小的赢if(quiet[ans[cur]]quiet[ans[next]]){ans[next]ans[cur];}// next 少欠一个上级欠账清零就轮到他了if(--indegree[next]0){queue[r]next;}}}returnans;}}代码大白话graph.get(r[0]).add(r[1])谁比谁有钱画一个箭头指向没钱的indegree[r[1]]被指的人欠一个通知indegree[i] 0入队没人比他有钱先算ans[i] i候选名单先只写自己quiet[ans[cur]] quiet[ans[next]]比谁更安静取数字小的--indegree[next] 0上级都通知完了轮到他C 版同一套思路C 把数组模拟的队列换成std::queue。classSolution{public:vectorintloudAndRich(vectorvectorintricher,vectorintquiet){intnquiet.size();// 建图箭头从有钱的指向没钱的vectorvectorintgraph(n);// indegree[i] 还有几个人直接比 i 有钱也就是 i 还欠几个通知vectorintindegree(n,0);for(autor:richer){graph[r[0]].push_back(r[1]);// r[0] 比 r[1] 更有钱连边 r[0] → r[1]indegree[r[1]];// r[1] 多欠一个上级}// 答案先全部设成自己vectorintans(n);for(inti0;in;i){ans[i]i;}// 没人比他有钱的人先入队他们不欠任何上级queueintq;for(inti0;in;i){if(indegree[i]0){q.push(i);}}while(!q.empty()){intcurq.front();q.pop();for(intnext:graph[cur]){// cur 比 next 有钱所以 cur 的答案也是 next 的合法候选if(quiet[ans[cur]]quiet[ans[next]]){ans[next]ans[cur];}// next 少欠一个上级欠账清零就轮到他了if(--indegree[next]0){q.push(next);}}}returnans;}};Python 版同一套思路Python 用deque当队列图存成嵌套列表。fromcollectionsimportdequeclassSolution:defloudAndRich(self,richer:list[list[int]],quiet:list[int])-list[int]:nlen(quiet)# 建图箭头从有钱的指向没钱的graph[[]for_inrange(n)]# indegree[i] 还有几个人直接比 i 有钱也就是 i 还欠几个通知indegree[0]*nfora,binricher:graph[a].append(b)# a 比 b 更有钱连边 a → bindegree[b]1# b 多欠一个上级# 答案先全部设成自己anslist(range(n))# 没人比他有钱的人先入队他们不欠任何上级qdeque(iforiinrange(n)ifindegree[i]0)whileq:curq.popleft()fornxtingraph[cur]:# cur 比 nxt 有钱所以 cur 的答案也是 nxt 的合法候选ifquiet[ans[cur]]quiet[ans[nxt]]:ans[nxt]ans[cur]# nxt 少欠一个上级欠账清零就轮到他了indegree[nxt]-1ifindegree[nxt]0:q.append(nxt)returnans为什么这样一定对轮到一个人的时候所有比他有钱的人都已经算过了。他们的答案顺着链条一层层传到他身上所以他开始算的时候拿到的就是最终答案不会再被改。换个说法整个过程就是按谁没有上级谁先算这个顺序往下推每个人都要等上级的通知收齐才算算完答案就定下来了。这也是拓扑排序类题目的共同点先处理没有依赖的处理完就解锁下一批。两个坑箭头方向别搞反richer[i] [a, b]说的是 a 比 b 更有钱箭头是a → b欠账加在b头上。方向反了欠账就算在了错误的人身上整道题全错。比较的是安静值不是编号用的是quiet[ans[cur]]先拿编号去查安静值再比大小。直接比ans[cur]就变成了比谁编号小跟题目要的安静程度没关系。复杂度n个人m条富有关系。每个人只算一次每条边走一次。时间O(n m)空间O(n m)。回头看这道题这道题最值得记的地方是欠账这个角度。面对一张有依赖关系的有向图最直白的想法是顺着链条去查但那样同一个答案会被反复算很多遍。换成谁没有依赖谁先算算完解锁下一批算出来的答案直接往下传没有回头重算。这就是拓扑排序。听起来像个算法名词说白了就是排队谁的事办完了谁就往前挪一格。
阅读完成 · 觉得有帮助？
