What is the core pattern used in Loud and Rich?

The problem relies on graph indegree computation combined with topological ordering to propagate quietness along richer-to-poorer edges.

Can DFS replace topological sort in this problem?

Yes, DFS with memoization can traverse richer paths to compute the quietest person while avoiding redundant calculations.

What is the maximum number of people supported efficiently?

The solution handles up to 500 people, consistent with constraints on array length and edge count.

How do we handle multiple richer paths to the same person?

Always update the quietest person by comparing existing quietness with propagated values along each incoming richer path.

Is the answer array guaranteed to contain unique indices?

Not necessarily; the same person may be the quietest for multiple individuals, depending on transitive richer relationships.

#851

Medium

auto_awesome图·搜索

LeetCode 题解工作台

喧闹和富有

有一组 n 个人作为实验对象，从 0 到 n - 1 编号，其中每个人都有不同数目的钱，以及不同程度的安静值（quietness）。为了方便起见，我们将编号为 x 的人简称为 "person x "。给你一个数组 richer ，其中 richer[i] = [a i , b i ] 表示 per…

数组深度优先搜索图拓扑排序

题目描述

有一组 n 个人作为实验对象，从 0 到 n - 1 编号，其中每个人都有不同数目的钱，以及不同程度的安静值（quietness）。为了方便起见，我们将编号为 x 的人简称为 "person x "。

给你一个数组 richer ，其中 richer[i] = [a_i, b_i] 表示 person a_i 比 person b_i 更有钱。另给你一个整数数组 quiet ，其中 quiet[i] 是 person i 的安静值。richer 中所给出的数据 逻辑自洽（也就是说，在 person x 比 person y 更有钱的同时，不会出现 person y 比 person x 更有钱的情况）。

现在，返回一个整数数组 answer 作为答案，其中 answer[x] = y 的前提是，在所有拥有的钱肯定不少于 person x 的人中，person y 是最不安静的人（也就是安静值 quiet[y] 最小的人）。

示例 1：

输入：richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0]
输出：[5,5,2,5,4,5,6,7]
解释： 
answer[0] = 5，
person 5 比 person 3 有更多的钱，person 3 比 person 1 有更多的钱，person 1 比 person 0 有更多的钱。
唯一较为安静（有较低的安静值 quiet[x]）的人是 person 7，
但是目前还不清楚他是否比 person 0 更有钱。
answer[7] = 7，
在所有拥有的钱肯定不少于 person 7 的人中（这可能包括 person 3，4，5，6 以及 7），
最安静（有较低安静值 quiet[x]）的人是 person 7。
其他的答案也可以用类似的推理来解释。

示例 2：

输入：richer = [], quiet = [0]
输出：[0]

提示：

n == quiet.length
1 <= n <= 500
0 <= quiet[i] < n
quiet 的所有值 互不相同
0 <= richer.length <= n * (n - 1) / 2
0 <= a_i, b_i < n
a_i!= b_i
richer 中的所有数对 互不相同
对 richer 的观察在逻辑上是一致的

lightbulb

解题思路

方法一：DFS

我们先用邻接表 $g$ 存储 $richer$ 数组中的信息，其中 $g[i]$ 表示所有比 $i$ 更有钱的人的集合。

然后对于每个人 $i$ ，我们用 DFS 遍历所有比 $i$ 更有钱的人，找到其中安静值最小的人，即为答案。

时间复杂度 $O(m + n)$ ，空间复杂度 $O(m + n)$ 。其中 $m$ 和 $n$ 分别为 $richer$ 数组和 $quiet$ 数组的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

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

speed

复杂度分析

指标	值
时间	complexity is \mathcal{O}(N^2) because each person may connect to multiple others in the graph and updates propagate along edges. Space complexity is \mathcal{O}(N^2) for storing the adjacency list and tracking quietest person per node during topological traversal.
空间	\mathcal{O}(N^2)

psychology

面试官常问的追问

外企场景

question_mark
Checking if you model richer relationships as a graph correctly.
question_mark
Looking for proper indegree computation and queue usage for topological sort.
question_mark
Ensuring quietness propagation follows the graph edges accurately.

warning

常见陷阱

外企场景

error
Failing to account for multiple richer paths leading to the same person and not updating quietness properly.
error
Confusing indegree direction and processing poorer-to-richer instead of richer-to-poorer.
error
Assuming the quietest person is always directly richer, ignoring transitive richer relationships.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Solve using DFS with memoization instead of explicit topological sorting.
arrow_right_alt
Handle cases where richer relationships may form multiple disconnected wealth chains.
arrow_right_alt
Adapt for dynamic updates where new richer relationships are added incrementally.

help

常见问题

外企场景

继续练习

#329 矩阵中的最长递增路径 #802 找到最终的安全状态 #924 尽量减少恶意软件的传播