每日一题——851. 喧闹和富有

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] 最小的人）。

public class Solution {
    public int[] LoudAndRich(int[][] richer, int[] quiet) {
        //构建一张有向图进行搜索
        int n = quiet.Length;
        IList<int>[] tree = new List<int>[n];
        for(int i=0;i<n;i++)
        {
            tree[i] = new List<int>();
        }

        foreach(int[] r in richer)
        {
            tree[r[1]].Add(r[0]);
            //注意是有向的，要指向比自己更有钱的人，所以是下标1指向下标0
        }

        int[] ans = new int[n];
        Array.Fill(ans,-1);
        //默认全是-1，主要是为了避免DFS重复运算
        for(int i = 0;i<n;i++)
        {
            DFS(i,quiet,tree,ans);
        }
        return ans;
        //采用深度优先
    }

    public void DFS(int x, int[] quiet, IList<int>[] tree, int[] ans)
    {
        if(ans[x] != -1)
        {
            return;//为了避免重复运算
        }
        ans[x] = x;
        foreach(int y in tree[x])
        {
            DFS(y,quiet,tree,ans);
            if(quiet[ans[y]] < quiet[ans[x]])
            {
                ans[x] = ans[y];
            }
        }
    }
}

谁比我有钱，就从我身上拉一条有向线段到谁身上

这样就会构成一个不闭环的有向图

接下来要做的事情就是遍历了

这里用深度优先会比较好一点

在遍历的过程中去比较每个节点身上带着的安静值

如果比自个身上的大，答案就要更新