题干
2374. 边积分最高的节点 - 力扣（LeetCode）
给你一个有向图，图中有 n 个节点，节点编号从 0 到 n - 1 ，其中每个节点都 恰有一条 出边。
图由一个下标从 0 开始、长度为 n 的整数数组 edges 表示，其中 edges[i] 表示存在一条从节点 i 到节点 edges[i] 的 有向 边。
节点 i 的 边积分 定义为：所有存在一条指向节点 i 的边的节点的 编号 总和。
返回 边积分 最高的节点。如果多个节点的 边积分 相同，返回编号 最小 的那个。
示例 1：
输入：edges = [1,0,0,0,0,7,7,5]
输出：7
解释：
- 节点 1、2、3 和 4 都有指向节点 0 的边，节点 0 的边积分等于 1 + 2 + 3 + 4 = 10 。
- 节点 0 有一条指向节点 1 的边，节点 1 的边积分等于 0 。
- 节点 7 有一条指向节点 5 的边，节点 5 的边积分等于 7 。
- 节点 5 和 6 都有指向节点 7 的边，节点 7 的边积分等于 5 + 6 = 11 。
节点 7 的边积分最高，所以返回 7 。
解法
看着是图的遍历，但是仔细一看就是一个非常简单的贪心。每次刷新记录最大值刷新最大值就好了。
妥妥的属于简单题
如下
原始代码如下（这是错误的）
第一，这里不需要map，map的效率没有初始化数组高
第二，这里的最大值，会溢出Integer.MAX_VALUE 因此需要用long来记录
public static int edgeScore1(int[] edges) {int max = 0;int maxindex = Integer.MAX_VALUE;Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < edges.length; i++) {int edge = edges[i];Integer value = map.getOrDefault(edge, 0);map.put(edge, value + i);if (max < value + i) {max = value + i;maxindex = edge;} else if (max == value + i) {if (maxindex > edge) {maxindex = edge;}}}return maxindex;}修改后如下
public static int edgeScore(int[] edges) {long[] dp = new long[edges.length]; // 随便取的名字long max = 0;int maxindex = Integer.MAX_VALUE;for (int i = 0; i < edges.length; i++) {int edge = edges[i]; // 取出指向的点dp[edge] += i; // 指向的点的累计加上i值if (max < dp[edge]) { // 更新最大值max = dp[edge];maxindex = edge;} else if (max == dp[edge]) { // 当前值和最大值相等判断下下标哪个更小if (maxindex > edge) {maxindex = edge;}}}return maxindex;}
