851. 喧闹和富有

描述

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

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

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

分析

构建财富由大指向小的的邻接表，从最富有的人（入度为0）开始遍历，
每遍历一个人都把比这个人更穷的人的最安静的人更新一下。
因为是从度为0的结点不断向内遍历，所以遍历的过程是财富从高向更低前进的，所以可以求得一个人比他富有的人中最安静的那个，不会漏掉比他更富有的人。

class Solution {public int[] loudAndRich(int[][] richer, int[] quiet) {int n = quiet.length;List<List<Integer>> adjoin = new ArrayList<>();int[] degree = new int[n];int[] ans = new int[n];Queue<Integer> que = new LinkedList<>();for(int i = 0; i < n; i++){adjoin.add(new ArrayList<>());}for(int i = 0; i < richer.length; i++) {adjoin.get(richer[i][0]).add(richer[i][1]);degree[richer[i][1]]++;}for(int i = 0; i < n; i++){if(degree[i] == 0){que.add(i);}//一个人的默认值应该是它自身ans[i] = i;}while(!que.isEmpty()){int size = que.size();for(int i = 0; i < size; i++){int num = que.poll();List<Integer> tmp = adjoin.get(num);for(int j : tmp){degree[j]--;if(degree[j] == 0){que.add(j);}//ans[num]肯定在财富上是比j大的，同时又是比num大于等于声音有最小的人，//如果ans[num]的声音比ans[j]的声音小，更新ans[j]。if(quiet[ans[num]] < quiet[ans[j]]){ans[j] = ans[num];}}}}return ans;}
}