朋友之前在腾讯做程序员，年薪 80万，去年 34岁考上了老家的事业编，在教育局工作，每个月工资6000块。他爸妈现在逢人就夸自己儿子有出息
老鬼约 3 分钟朋友以前在大厂写代码，一年拿八十来万，放哪儿都算混得不错吧。结果去年三十多岁回老家考了个事业编，去了教育局，工资一下变成每月六千。
更好笑的是，他爸妈态度直接大反转。
以前儿子在腾讯上班，赚得多，他们也觉得脸上有光。现在不一样了，逢人就说儿子有出息了，进体制了，工作稳，说出去也体面，以后养老都不用愁。
你说钱重要吧，八十万摆在那儿。你说面子重要吧，在老一辈眼里，编制两个字好像自带光环，工资少点都不算事。
只能说，大厂光环再亮，在县城亲戚饭桌上，可能真不如一句“在教育局上班”。
richer[i] = [a, b] 这种输入，第一眼别急着把它当普通排序题。
它说的是：a 比 b 有钱。
但题目要问的是：对每个人 x，在所有“比他有钱的人 + 他自己”里面，谁最安静。
这地方我一般不会先想怎么排序财富。财富大小其实没给具体数值，只给了关系。你手里拿到的不是数组，是一张有向图。
比如：
richer = [[1,0],[2,1],[3,1]]
quiet = [5,3,8,1]
1 -> 0 表示 1 比 0 富有。
如果站在 0 的角度看，0 能往上找到 1，1 又能往上找到 2、3。
所以 0 的候选人其实是：
0, 1, 2, 3
再从 quiet 里面找最小值，答案就是 3。
这里最容易写别扭的地方，是建图方向。
我建议这样建：
poor -> rich
也就是如果 a 比 b 富有，就让 b 指向 a。
因为题目问的是“谁比我富有”，从当前人出发，一路往上找就行。
代码不要写成每个人都暴力扫一遍 richer。那样数据稍微大一点，就变成重复爬楼。比如 0 查过 1 的答案，后面再查 2、3 时又重新查，没必要。
这题用 DFS + 记忆化就很顺。
每个人的答案算一次，后面直接拿缓存。
Java 代码如下：
import java.util.*;
classSolution{
private List<Integer>[] richerGraph;
privateint[] quiet;
privateint[] best;
publicint[] loudAndRich(int[][] richer, int[] quiet) {
int n = quiet.length;
this.quiet = quiet;
this.best = newint[n];
Arrays.fill(best, -1);
richerGraph = new ArrayList[n];
for (int i = 0; i < n; i++) {
richerGraph[i] = new ArrayList<>();
}
for (int[] edge : richer) {
int rich = edge[0];
int poor = edge[1];
richerGraph[poor].add(rich);
}
int[] ans = newint[n];
for (int person = 0; person < n; person++) {
ans[person] = findQuietest(person);
}
return ans;
}
privateintfindQuietest(int person){
if (best[person] != -1) {
return best[person];
}
int candidate = person;
for (int rich : richerGraph[person]) {
int richBest = findQuietest(rich);
if (quiet[richBest] < quiet[candidate]) {
candidate = richBest;
}
}
best[person] = candidate;
return candidate;
}
}
这里 findQuietest(person) 的含义很清楚：从 person 出发，沿着“比他富有”的边一直往上找，返回这批人里最安静的那个编号。
有个细节别忽略：
best[person] = candidate;
这行就是记忆化。
没有它，代码也能跑，但会反复查同一批富人链路。这个题的关系可能会重叠很多，缓存一加，整个图基本就只走一遍。
执行过程大概是这样：
查 0
发现 1 比 0 富
查 1
发现 2 比 1 富
发现 3 比 1 富
得到 1 的最安静候选
再和 0 自己比较
得到 0 的答案
这其实就是在图上做递归合并。
时间复杂度是 O(n + m)，n 是人数，m 是 richer 关系数量。每个人只计算一次，每条边最多走一次。
这个题不用硬套最短路，也不用真给财富排序。关系已经给你了，顺着关系往上找，把每个人上游最安静的人缓存下来，就够了。