喧闹和富有 图解题解

这道题到底在问什么

输入

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 最小）

最优解：一步一步想明白

1. 3记住三件事:边指向更富的人;一个人的答案是他和所有更富邻居答案里最安静的;算过就缓存,绝不重复。
2. 4目标：每个人找出「钱不少于他的人」里最安静的那个先把这张图看懂。六个圆圈是六个人，圈里的数字是编号 0 到 5，圈旁边那个小数字是他的安静值，数字越小代表越安静。箭头表示「更富」的方向：箭头从穷的一方指向更富的一方。比如 0 号指向 1 号，意思是 1 号比 0 号有钱。题目要的是：对每个人 x，在所有钱不少于他的人里面，找出安静值最小、也就是最安静的那一个。提前说一句答案，最后这六个人的结果会是 5、5、2、5、4、5，下面一步步把它推出来。
3. 5从穷的一方连一条边到更富的一方动手之前先说清楚边是怎么建的。题目给的是一对一对的关系，每对说「某人比某人更富」。我们的做法是,从穷的那个人,连一条边指向更富的那个人。这样建完图,从任何一个人出发,顺着箭头能走到的,全是钱不比他少的人。0 号能走到 1 号,1 号能走到 2 号和 3 号,3 号又能走到 4 号和 5 号。我们要在这条能到达的范围里挑最安静的人,这正好是一次深度优先搜索能解决的事。
4. 6ans[0] 先记为 0号自己（静3）外层循环从 0 号开始,调用 dfs(0)。0 号还没算过,先把它的答案暂时记成自己,因为「钱不少于自己的人」至少包含他本人。把 0 号压进递归调用栈,标成紫色表示正在处理。右边面板就是这个调用栈,栈顶在最上面。接着要顺着 0 号的箭头,去看比他更富的人里有没有更安静的。
5. 70号 → 对更富的 1号 递归0 号只有一条边,指向更富的 1 号。在更新自己的答案之前,得先知道 1 号那边的最终答案是谁。所以暂停 0 号,先一头扎进 1 号,1 号被标成待探索的橙色。这就是深度优先:遇到一个更富的邻居,先把它整支彻底算完,再回头。
6. 8ans[1] 先记为 1号自己（静5）进入 dfs(1)。1 号也没算过,同样先把答案记成自己 1 号。现在调用栈里有 0 号和 1 号两层,栈顶是 1 号,正在处理。1 号有两条边,分别指向更富的 2 号和 3 号,我们按顺序先看 2 号。
7. 91号 → 对更富的 2号 递归1 号的第一条边指向更富的 2 号。先递归进 2 号,看它的答案是谁。0 号和 1 号都停在栈里排队等,2 号被点亮成橙色准备进入。
8. 10ans[2] 先记为 2号自己（静4）进入 dfs(2)。2 号答案先记成自己。注意 2 号没有任何指出去的箭头,也就是说没有比他更富的人了,他这一支到头了。下一帧直接给他定答案。
9. 11ans[2] 定为 2号（静4）2 号没有更富的邻居,能到达的就只有他自己,所以最安静的就是 2 号本人。ans[2] 定为 2 号,他的安静值是 4。2 号变绿表示答案已经确定,从调用栈里弹出。控制权交回给在等他的 1 号。
10. 12ans[1] = 2号（静4）回到 1 号。刚才 2 号那一支算出来最安静是 2 号,安静值 4;而 1 号自己的安静值是 5。4 比 5 小,2 号更安静,于是把 1 号的暂定答案从自己换成 2 号。1 号的活还没干完,它还有第二条边没看。
11. 131号 → 对更富的 3号 递归1 号的第二条边指向更富的 3 号。和刚才一样,先递归进 3 号把它整支算完,再回来跟现在的暂定答案 2 号比。3 号点亮成橙色。
12. 14ans[3] 先记为 3号自己（静2）进入 dfs(3)。3 号答案先记成自己,安静值 2。3 号有两条边,指向更富的 4 号和 5 号。调用栈现在堆到了三层:0 号、1 号、3 号,栈顶是 3 号。先看 3 号的第一个邻居 4 号。
13. 153号 → 对更富的 4号 递归3 号的第一条边指向更富的 4 号。递归进 4 号。栈里 0、1、3 号都在等。
14. 16ans[4] 先记为 4号自己（静1）进入 dfs(4)。4 号答案先记成自己,安静值是 1,挺安静的。4 号没有指出去的边,是这一支的尽头,下一帧定答案。
15. 17ans[4] 定为 4号（静1）4 号没有更富的邻居,最安静的只能是他自己。ans[4] 定为 4 号,安静值 1。4 号变绿,弹出调用栈,控制权回到 3 号。
16. 18ans[3] = 4号（静1）回到 3 号。4 号那支算出最安静是 4 号,安静值 1;3 号自己安静值是 2。1 比 2 小,4 号更安静,把 3 号的暂定答案从自己换成 4 号。3 号还有第二条边没看。
17. 193号 → 对更富的 5号 递归3 号的第二条边指向更富的 5 号。再递归进 5 号,算完它再跟当前暂定的 4 号比一比。
18. 20ans[5] 先记为 5号自己（静0）进入 dfs(5)。5 号答案先记成自己,安静值是 0,是全场最安静的。5 号也没有指出去的边,到头了。
19. 21ans[5] 定为 5号（静0）5 号没有更富的邻居,最安静的就是他自己。ans[5] 定为 5 号,安静值 0。5 号变绿弹出,控制权回到 3 号。
20. 22ans[3] = 5号（静0）回到 3 号。5 号那支算出最安静是 5 号,安静值 0;3 号现在暂定的是 4 号,安静值 1。0 比 1 还小,5 号更安静,把 3 号的答案换成 5 号。3 号两条边都看完了,可以定答案了。
21. 23ans[3] 定为 5号（静0）3 号的两个更富邻居都比较过了,最安静的是 5 号。ans[3] 定为 5 号,安静值 0。3 号变绿弹出调用栈,控制权回到一直在等它的 1 号。
22. 24ans[1] = 5号（静0）回到 1 号。3 号那一整支的答案是 5 号,安静值 0;而 1 号现在暂定的是 2 号,安静值 4。0 比 4 小,5 号更安静,把 1 号的答案从 2 号换成 5 号。1 号两条边都看完了。
23. 25ans[1] 定为 5号（静0）1 号的活干完了,它能到达的人里最安静的是 5 号。ans[1] 定为 5 号,安静值 0。1 号变绿弹出,控制权回到最早在等的 0 号。
24. 26ans[0] = 5号（静0）回到最初的 0 号。1 号那支的答案是 5 号,安静值 0;0 号自己安静值是 3。0 比 3 小,5 号更安静,把 0 号的答案换成 5 号。0 号只有这一条边,看完了。
25. 27ans[0] 定为 5号（静0）dfs(0) 这一整趟级联全部回来了。0 号能到达的人里最安静的是 5 号。ans[0] 定为 5 号。0 号变绿。注意这一趟下来,0、1、2、3、4、5 六个人的答案竟然全都顺手算出来了。
26. 28ans[1] 已算过，直接跳过外层循环继续走到 1 号,调用 dfs(1)。但 1 号刚才在 0 号那趟级联里已经算过,答案就是 5 号。代码开头那句「如果已经算过就直接返回」在这里生效,1 号一秒跳过,不会重复递归。这就是记忆化的意义。
27. 292号~5号都已算过,直接跳过外层循环再往后走到 2、3、4、5 号,它们的答案也全在刚才那趟里定好了,每一个都命中记忆化,直接返回,不再展开任何递归。正因为有这层缓存,每个人的答案只会被真正计算一次,每条边也只会被走一次。要是没有这层记忆化,像 0 号这种顶层节点会把下面整片重复算很多遍,复杂度会爆炸。
28. 30答案 answer = [5,5,2,5,4,5]六个人全部变绿,答案凑齐了:0 号到 5 号依次是 5、5、2、5、4、5。回头验一眼最关键的 0 号:它能到达 1、2、3、4、5 全部人,这些人加上他自己里面,安静值最小的是 5 号的 0,所以 ans[0] 是 5,对得上。而 2 号谁也到不了,答案只能是自己。整道题就是一句话:建图把边指向更富的人,再用一次带记忆化的深度优先,在能到达的范围里挑最安静的那个。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from 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

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) {
        int n = quiet.size();
        vector<vector<int>> g(n);
        for (auto& r : richer) {
            g[r[1]].push_back(r[0]);
        }
        vector<int> ans(n, -1);
        function<void(int)> dfs = [&](int i) {
            if (ans[i] != -1) {
                return;
            }
            ans[i] = i;
            for (int j : g[i]) {
                dfs(j);
                if (quiet[ans[j]] < quiet[ans[i]]) {
                    ans[i] = ans[j];
                }
            }
        };
        for (int i = 0; i < n; ++i) {
            dfs(i);
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    private List<Integer>[] g;
    private int n;
    private int[] quiet;
    private int[] ans;

    public int[] loudAndRich(int[][] richer, int[] quiet) {
        n = quiet.length;
        this.quiet = quiet;
        g = new List[n];
        ans = new int[n];
        Arrays.fill(ans, -1);
        Arrays.setAll(g, k -> new ArrayList<>());
        for (int[] r : richer) {
            g[r[1]].add(r[0]);
        }
        for (int i = 0; i < n; ++i) {
            dfs(i);
        }
        return ans;
    }

    private void dfs(int i) {
        if (ans[i] != -1) {
            return;
        }
        ans[i] = i;
        for (int j : g[i]) {
            dfs(j);
            if (quiet[ans[j]] < quiet[ans[i]]) {
                ans[i] = ans[j];
            }
        }
    }
}

复杂度

面试官可能追问