§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

思路解析

一句话答案：LeetCode 851 喧闹和富有：把边反向建图、让每个人指向更富的邻居，再用记忆化 DFS 求出 i 和所有更富者里最安静的那个，每人只算一次，时间 O(n+m)。

每个人要找『不比他穷的人』里最安静的

n 个人，每人一个互不相同的安静值 quiet[i]；richer[i]=[a,b] 表示 a 比 b 有钱。要为每个人 x 求 answer[x]：所有钱不少于 x 的人里，含 x 自己，安静值最小者的编号。题面 richer=[[1,0],[2,1],[3,1],[4,3],[5,3]]、quiet=[3,5,4,2,1,0]，答案 [5,5,2,5,4,5]。0 号能牵连到 5 号，5 号安静值 0 最小，所以 answer[0]=5。

每人都从自己出发爬一遍更富的人，慢在哪

给每个人单独算，就是从他出发顺着『更富』一层层爬，收齐能到的人再挑最安静的。可 0 号要爬全部五人、1 号要爬 2、3、4、5，路径大量重叠，同一片子图反复走，次数从线性涨到指数。

反向建图，让每个人指向更富的邻居

重复全在每次重新爬，得让算过的结果存下来复用。题目说『a 比 b 富』，我们反着存：把边掉个方向，从穷的 b 连一条指向更富的 a，这样从谁出发顺箭头走到的都是钱不比他少的人。于是 answer[i] 就是 i 自己和每个更富邻居各自答案里最安静的一个——邻居的答案已涵盖它能牵连的更富者，只看直接邻居就够。

dfs(i) 先算完更富的邻居再回头比

代码是一个带记忆化的 dfs，即先钻进一个更富邻居、把那一支算完就看下一个。记忆化，就是算过的结果存下来不重算：ans 数组全填 -1 当『没算过』记号，ans[i] 不是 -1 就直接返回。dfs(i) 先把 ans[i] 记成自己，因为钱不少于自己的至少有本人；再遍历更富邻居 j，先递归 dfs(j) 算完那一支，只要 quiet[ans[j]]＜quiet[ans[i]] 就把 ans[i] 换成 ans[j]。外层对每人调一次 dfs，真正展开只有第一次。

六个人这张图，答案怎么一趟全定下来

跟着题面走。反向建图后 g[0]=[1]、g[1]=[2,3]、g[3]=[4,5]，2、4、5 号没有出边。dfs(2) 无邻居，ans[2]=2；回到 1 号，quiet[2]=4＜quiet[1]=5，1 号暂定 2 号。dfs(3) 先钻 4，ans[4]=4，quiet[4]=1＜quiet[3]=2；再钻 5，ans[5]=5，quiet[5]=0＜quiet[4]=1，得 ans[3]=5。回到 1 号，quiet[5]=0＜quiet[2]=4，ans[1]=5；回到 0 号，quiet[5]=0＜quiet[0]=3，ans[0]=5。六人一趟全定好，其余全命中缓存直接返回，凑出 [5,5,2,5,4,5]。

复杂度是线性的，三个坑别踩

时间 O(n+m)：建图是 O(m)，记忆化让每人只算一次、每条边只走一次；空间 O(n+m)，邻接表、答案数组加最坏一条长链的递归栈。三处最容易写坏：箭头得从穷指向富，指错了会滑到更穷的人、编号全错；别省记忆化，漏了那句提前返回，顶层会把下面整片重复展开，复杂度退回指数；别被『富有』带偏，要的是最安静而非最有钱。没有更富关系时答案是自己，走到头的节点也是自己。

▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开

记住三件事:边指向更富的人;一个人的答案是他和所有更富邻居答案里最安静的;算过就缓存,绝不重复。

先把这张图看懂。六个圆圈是六个人，圈里的数字是编号 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 开通年卡 →

想成体系刷透这类套路？去图解算法专题

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