标签： 深度优先搜索

输入：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。
其他的答案也可以用类似的推理来解释。

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

DFS，还可以再优化下

1. 遍历int[][] richer数组，生成一个map，构建当前节点和比他小的person节点的关联关系
2. 在遍历的过程中，同时知道了哪些节点没有比他大的节点，存放于HashSet<Integer> starter中
3. 从starter遍历逐个进行DFS，利用int[] quiet数组中对应的喧嚣值往下深搜的时候代入更新到结果int[] ans数组中
4. 由于在初始化的时候赋值了Arrays.fill(ans,501)每个值为501，所以如果当前喧嚣值比当前的ans[i]大或者等于的话就不用继续往下更新了
5. 最终int[] ans数组中存的是当前对应的quiet值，又因为quiet 的所有值 互不相同所以根据反向映射关系重新赋值更新为对应的person
6. 其实int[] ans中也可以一开始就存对应的person,不用最终再转换一遍，但是一开始用quiet来比较运算比较直观点，所以就先这么写了
7. 最终结果返映射的时候，如果当前ans[i]依然等于501，说明这个点是独立的，不和其他点有相关联，那么对应依旧为quiet[i]
8. int[] ans数组也可以一开始就等于int[] quiet数组，但是这样的话再dfs过程中判断大小的时候需要再借助其他手段判断是否需要再往下层更新

代码

class Solution {

//     richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]],
//     quiet = [3,2,5,4,6,1,7,0]
//        6    5
//        ↓  ↙
//    2   3  ←  4
//    ↓ ↙   ↘
//    1       7
//    ↓
//    0

    HashMap<Integer, HashSet<Integer>> map = new HashMap<>();
    int[] ans;
    int[] quiet;
    int[] quietToPerson;

    public int[] loudAndRich(int[][] richer, int[] quiet) {
        this.quiet = quiet;
        ans = new int[quiet.length];
        Arrays.fill(ans,501);
        quietToPerson = new int[quiet.length];
        for (int i = 0; i < quiet.length; i++) {
            quietToPerson[quiet[i]] = i;
        }

        HashSet<Integer> starter = new HashSet<>();
        for (int[] ints : richer) {
            if (!map.containsKey(ints[0])){
                map.put(ints[0],new HashSet<>());
            }
            map.get(ints[0]).add(ints[1]);
            starter.remove(ints[1]);
            starter.add(ints[0]);
        }
        starter.forEach(i -> {
            dfs(i,quiet[i]);
        });

        for (int i = 0; i < ans.length; i++) {
            ans[i]= quietToPerson[ans[i]>500?quiet[i]:ans[i]];
        }
        return ans;
    }

    public void dfs(int num, int min){
        if (min > quiet[num]){
            min = quiet[num];
        }
        if (ans[num] > min){
            ans[num] = min;
        }else{
            return;
        }
        if (map.containsKey(num)){
            int finalMin = min;
            map.get(num).forEach(integer -> {
                dfs(integer, finalMin);
            });
        }
    }
}