前言
大家好我是bigsai。
今天给大家分享一个非常有趣的面试题，通过这个问题你可能会对某些情况下，搜索和拓扑有一定的认识，一个问题，既可以用搜索来处理，用记忆化搜索优化，也可以用拓扑排序来解决。
题目为力扣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] 最小的人）
理解题意
这个问题其实要理解题意还是需要一点时间的，我也读了不少时间才搞明白(原谅我语文很差)。
题目大概的意思是：题目告诉你一堆关系，对就是谁比谁有钱。
举个例子，你们宿舍4个人，不是谁跟谁关系都很好，有的私交不一定很深。
你是江苏某穷乡僻壤来的，为人很害羞不跟人说话，只跟省会南京的一个舍友聊天，南京舍友跟你说他是南京城里土著你就知道他比你有钱了……。南京舍友跟北京舍友聊天得知北京舍友四合院卧槽北京舍友有钱，南京舍友跟上海舍友聊天得知上海舍友有好几套房肯定比它有钱，但北上两舍友性格不合没聊过家里啥情况互相不敢猜测谁比谁有钱。
所以你们宿舍形成这样一个关系：
但是这里面有两种评判标准构造这个逻辑，一个是比我穷，一个是比我有钱，究竟怎么使用我们继续看题意。
题目说每个人有个低调值(简单说啦)，然后每个人要找到这个逻辑中比自己有钱(包括自己)最低调的人。
比我有钱的角度
如果从比我有钱角度出发， 那么每次都要进行搜索，根据这个顺序结构找到比我有钱的最低调的人，比如看最上面从你出发，找南京知道的最低调的有钱人。但是这个步骤使用搜索递归，这4个人你看不出来，如果说你们宿舍5个人，有个山沟沟的舍友比你还穷，他搜索时候：你、南京舍友、{北京，上海搜索分叉}。然后到你的时候，又是：南京舍友、{北京，上海搜索分叉}，这样重复计算效率很低啊。这就可以用记忆化搜索，搜过一遍记下来。
代码我没写，没用这个方法。因为搜索是从少的情况搜索更多未知的内容，会有比较多的重复计算，所以记忆化搜索就比较重要了。
比我穷的角度
从比我穷的角度来看，我是可以直接改变直接比我穷的那个人的低调值指向的，这个比我穷的角度就是拓扑排序了，例如上面北京舍友或者上海舍友肯定第一个。
假如北京舍友第一个，拓扑找到比我穷的南京舍友，然后看看我的低调值是不是比它的低，如果比他低，那么南京舍友低调值换成我的，并且低调指向编号是我。
然后上海舍友第二个，虽然你被北京舍友摩擦过但是不影响，上海舍友希望将南京舍友从北京小伙手中夺过来(有可能南京小伙本身非常低调没被感染)，然后上海小伙三顾茅庐低调值比被感染过得南京舍友还低，那南京舍友还等什么，直接低调值跟随上海舍友，低调值指向上海舍友位置。
然后第三个南京舍友，他此时低调值非常低了(因为前面北上和他自己三个最低就是他)，如果他低调值比你低，你低调值变成他一样，然后指向他指向的对应位置。
这就是一个拓扑排序的过程，这里面几个细节：
低调值改变：你可能直接支配比你穷的人，你一旦支配比你穷的，比你穷还穷的那些人很可能也被你支配，你的很低的低调值和位置需要被传递下去，所以需要一些标记。
附上代码：
class Solution { public int[] loudAndRich(int[][] richer, int[] quiet) { int len=quiet.length; List<Integer> next[]=new ArrayList[len];//记录指向的集合 int inDegree[]=new int[len];//记录入度 int value[]=new int[len]; for(int i=0;i<len;i++){ next[i]=new ArrayList<>(); value[i]=i; } for(int i=0;i<richer.length;i++){ int rich=richer[i][0]; int poor=richer[i][1]; next[rich].add(poor); inDegree[poor]++; } Queue<Integer>queue=new ArrayDeque<>(); for(int i=0;i<len;i++){ if(inDegree[i]==0) queue.add(i); } while (!queue.isEmpty()){ int rich=queue.poll(); for(int poor:next[rich]){ inDegree[poor]--; if(quiet[rich]<quiet[poor]){ quiet[poor]=quiet[rich]; value[poor]=value[rich]; } if(inDegree[poor]==0){ queue.add(poor); } } } return value; } }
这样，这个问题就解决啦。
