§1
题目描述
n 个人编号 0 到 n-1,每人有一个互不相同的安静值 quiet[i]。给一个数组 richer,richer[i]=[a,b] 表示 a 比 b 更有钱(关系逻辑自洽,不会出现互相更富的矛盾)。返回数组 answer,其中 answer[x] 是「所有钱不少于 person x 的人(包含 x 自己)」当中安静值最小的那个人的编号。数据范围 1 ≤ n ≤ 500,安静值互不相同。
输入 = richer=[[1,0],[2,1],[3,1],[4,3],[5,3]], quiet=[3,5,4,2,1,0] 输出 = [5,5,2,5,4,5]（如 answer[0]=5:0 号顺着更富关系能牵连到 5 号,5 号安静值 0 最小）
§2
思路解析动画文字版
记住三件事:边指向更富的人;一个人的答案是他和所有更富邻居答案里最安静的;算过就缓存,绝不重复。
先把这张图看懂。六个圆圈是六个人，圈里的数字是编号 0 到 5，圈旁边那个小数字是他的安静值，数字越小代表越安静。箭头表示「更富」的方向：箭头从穷的一方指向更富的一方。比如 0 号指向 1 号，意思是 1 号比 0 号有钱。题目要的是：对每个人 x，在所有钱不少于他的人里面，找出安静值最小、也就是最安静的那一个。提前说一句答案，最后这六个人的结果会是 5、5、2、5、4、5，下面一步步把它推出来。
动手之前先说清楚边是怎么建的。题目给的是一对一对的关系，每对说「某人比某人更富」。我们的做法是,从穷的那个人,连一条边指向更富的那个人。这样建完图,从任何一个人出发,顺着箭头能走到的,全是钱不比他少的人。0 号能走到 1 号,1 号能走到 2 号和 3 号,3 号又能走到 4 号和 5 号。我们要在这条能到达的范围里挑最安静的人,这正好是一次深度优先搜索能解决的事。
进入 dfs(0)
外层循环从 0 号开始,调用 dfs(0)。0 号还没算过,先把它的答案暂时记成自己,因为「钱不少于自己的人」至少包含他本人。把 0 号压进递归调用栈,标成紫色表示正在处理。右边面板就是这个调用栈,栈顶在最上面。接着要顺着 0 号的箭头,去看比他更富的人里有没有更安静的。
看更富的邻居 1号
0 号只有一条边,指向更富的 1 号。在更新自己的答案之前,得先知道 1 号那边的最终答案是谁。所以暂停 0 号,先一头扎进 1 号,1 号被标成待探索的橙色。这就是深度优先:遇到一个更富的邻居,先把它整支彻底算完,再回头。
进入 dfs(1)
进入 dfs(1)。1 号也没算过,同样先把答案记成自己 1 号。现在调用栈里有 0 号和 1 号两层,栈顶是 1 号,正在处理。1 号有两条边,分别指向更富的 2 号和 3 号,我们按顺序先看 2 号。
看更富的邻居 2号
1 号的第一条边指向更富的 2 号。先递归进 2 号,看它的答案是谁。0 号和 1 号都停在栈里排队等,2 号被点亮成橙色准备进入。
进入 dfs(2)
进入 dfs(2)。2 号答案先记成自己。注意 2 号没有任何指出去的箭头,也就是说没有比他更富的人了,他这一支到头了。下一帧直接给他定答案。
确定 ans[2]
2 号没有更富的邻居,能到达的就只有他自己,所以最安静的就是 2 号本人。ans[2] 定为 2 号,他的安静值是 4。2 号变绿表示答案已经确定,从调用栈里弹出。控制权交回给在等他的 1 号。
回到 1 号。刚才 2 号那一支算出来最安静是 2 号,安静值 4;而 1 号自己的安静值是 5。4 比 5 小,2 号更安静,于是把 1 号的暂定答案从自己换成 2 号。1 号的活还没干完,它还有第二条边没看。
看更富的邻居 3号
1 号的第二条边指向更富的 3 号。和刚才一样,先递归进 3 号把它整支算完,再回来跟现在的暂定答案 2 号比。3 号点亮成橙色。
进入 dfs(3)
进入 dfs(3)。3 号答案先记成自己,安静值 2。3 号有两条边,指向更富的 4 号和 5 号。调用栈现在堆到了三层:0 号、1 号、3 号,栈顶是 3 号。先看 3 号的第一个邻居 4 号。
看更富的邻居 4号
3 号的第一条边指向更富的 4 号。递归进 4 号。栈里 0、1、3 号都在等。
进入 dfs(4)
进入 dfs(4)。4 号答案先记成自己,安静值是 1,挺安静的。4 号没有指出去的边,是这一支的尽头,下一帧定答案。
确定 ans[4]
4 号没有更富的邻居,最安静的只能是他自己。ans[4] 定为 4 号,安静值 1。4 号变绿,弹出调用栈,控制权回到 3 号。
回到 3 号。4 号那支算出最安静是 4 号,安静值 1;3 号自己安静值是 2。1 比 2 小,4 号更安静,把 3 号的暂定答案从自己换成 4 号。3 号还有第二条边没看。
看更富的邻居 5号
3 号的第二条边指向更富的 5 号。再递归进 5 号,算完它再跟当前暂定的 4 号比一比。
进入 dfs(5)
进入 dfs(5)。5 号答案先记成自己,安静值是 0,是全场最安静的。5 号也没有指出去的边,到头了。
确定 ans[5]
5 号没有更富的邻居,最安静的就是他自己。ans[5] 定为 5 号,安静值 0。5 号变绿弹出,控制权回到 3 号。
回到 3 号。5 号那支算出最安静是 5 号,安静值 0;3 号现在暂定的是 4 号,安静值 1。0 比 1 还小,5 号更安静,把 3 号的答案换成 5 号。3 号两条边都看完了,可以定答案了。
确定 ans[3]
3 号的两个更富邻居都比较过了,最安静的是 5 号。ans[3] 定为 5 号,安静值 0。3 号变绿弹出调用栈,控制权回到一直在等它的 1 号。
回到 1 号。3 号那一整支的答案是 5 号,安静值 0;而 1 号现在暂定的是 2 号,安静值 4。0 比 4 小,5 号更安静,把 1 号的答案从 2 号换成 5 号。1 号两条边都看完了。
确定 ans[1]
1 号的活干完了,它能到达的人里最安静的是 5 号。ans[1] 定为 5 号,安静值 0。1 号变绿弹出,控制权回到最早在等的 0 号。
回到最初的 0 号。1 号那支的答案是 5 号,安静值 0;0 号自己安静值是 3。0 比 3 小,5 号更安静,把 0 号的答案换成 5 号。0 号只有这一条边,看完了。
确定 ans[0]
dfs(0) 这一整趟级联全部回来了。0 号能到达的人里最安静的是 5 号。ans[0] 定为 5 号。0 号变绿。注意这一趟下来,0、1、2、3、4、5 六个人的答案竟然全都顺手算出来了。
记忆化命中 · 1号
外层循环继续走到 1 号,调用 dfs(1)。但 1 号刚才在 0 号那趟级联里已经算过,答案就是 5 号。代码开头那句「如果已经算过就直接返回」在这里生效,1 号一秒跳过,不会重复递归。这就是记忆化的意义。
外层循环再往后走到 2、3、4、5 号,它们的答案也全在刚才那趟里定好了,每一个都命中记忆化,直接返回,不再展开任何递归。正因为有这层缓存,每个人的答案只会被真正计算一次,每条边也只会被走一次。要是没有这层记忆化,像 0 号这种顶层节点会把下面整片重复算很多遍,复杂度会爆炸。
完成 · 对照答案
六个人全部变绿,答案凑齐了:0 号到 5 号依次是 5、5、2、5、4、5。回头验一眼最关键的 0 号:它能到达 1、2、3、4、5 全部人,这些人加上他自己里面,安静值最小的是 5 号的 0,所以 ans[0] 是 5,对得上。而 2 号谁也到不了,答案只能是自己。整道题就是一句话:建图把边指向更富的人,再用一次带记忆化的深度优先,在能到达的范围里挑最安静的那个。
边界想清:没有更富关系时人人答案是自己;到头的节点也是自己;自己最安静时答案就是自己。
面试重点:除 DFS 外还有拓扑排序解法;更富关系自洽保证是有向无环图,递归不会绕圈。
§3
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]: def dfs(i: int): if ans[i] != -1: return ans[i] = i for j in g[i]: dfs(j) if quiet[ans[j]] < quiet[ans[i]]: ans[i] = ans[j] g = defaultdict(list) for a, b in richer: g[b].append(a) n = len(quiet) ans = [-1] * n for i in range(n): dfs(i) return ans看懂代码不等于写得出。盖住上面，自己默写一遍试试。卡在哪一行说不清，就点右下角问小欧。
§4
复杂度
- 时间：O(n + m)，n 是人数,m 是 richer 的对数。建图遍历 m 对是 O(m);深度优先靠记忆化,每个人的答案只真正计算一次,每条边也只被走一次,合计 O(n + m)
- 空间：O(n + m)，邻接表存全部边是 O(n + m);答案数组 O(n);递归调用栈最坏(关系连成一条长链)深度到 O(n)
§5
易错点
✗ 错误写法：把边建反,从富指向穷
✓ 正确写法：要从穷指向富,即 g[b] 里放 a
我们要找的是「钱不少于自己」的人,沿边必须能走向更富的方向,反了就找错人
✗ 错误写法：不做记忆化,每次从头递归
✓ 正确写法：ans[i] 不是 -1 就直接返回
顶层节点会把下面整片重复展开很多遍,复杂度从线性退化到指数级
✗ 错误写法：以为答案是更富的人里最有钱的
✓ 正确写法：要的是安静值最小、最安静的那个
题目问的是 quiet 最小,跟钱多少无关,别被「富有」二字带偏
§
面试追问把动画讲成自己的话
追问这题除了 DFS 加记忆化,还有别的解法吗?
有,用拓扑排序加 BFS 也很自然。注意它要把边反过来建成「富→穷」:对每对 [a,b](a 比 b 富)连一条 a→b,再统计每个人的入度,也就是还有多少更富的来源没处理。从入度为 0、也就是没有更富来源的最富的人开始,把当前已知最安静的候选沿 a→b 传给更穷的邻居;某人入度减到 0 时,说明所有比他富的人都处理完了,他就拿到了最终答案。两种解法复杂度都是 O(n + m),DFS 写起来更短,拓扑排序的好处是天然没有递归深度的担忧。
追问为什么这题的图一定不会有环,可以放心递归?
因为题目明确说更富关系逻辑自洽,不会出现 a 比 b 富同时 b 又比 a 富这种矛盾。richer 关系无矛盾,顺着「更富」方向连边就不可能绕回来,建出来的图本质是一张有向无环图(DAG)。没有环就意味着 DFS 不会无限绕圈,记忆化也能保证每个点只算一次,递归一定会终止。
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
下一题 · 图论套路 33/85
→翻转矩阵后的得分
LeetCode 861 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
899道动画图解
28课数据结构
¥0.27折合 / 天
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
¥99 开通年卡 →
想成体系刷透这类套路？去图解算法专题