Kimi LeetCode 3547. 图中边值的最大和 Java实现
以下是 LeetCode 3547. 图中边值的最大和 的 Java 实现。
解题思路
由于每个节点最多与其他两个节点相连，整个图由若干链和环组成。核心贪心策略：
1. 先处理环，再处理链——环的每节点度数为 2，能贡献更多边权；链至少有一个端点度数为 1。
2. 链按长度降序处理——长链能贡献更多边，优先分配大数。
3. 填数策略——将剩余的最大数放在连通分量的中间，次大的数交替向两边扩展，使得大数尽量相邻（类似排序不等式）。
时间复杂度 O(n \log n)，空间复杂度 O(n)。
---
Java 代码
```java
import java.util.*;
class Solution {
public long maxScore(int n, int[][] edges) {
long ans = 0;
// 建图
List<Integer>[] graph = new List[n];
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList<>();
}
for (int[] edge : edges) {
int u = edge[0], v = edge[1];
graph[u].add(v);
graph[v].add(u);
}
boolean[] seen = new boolean[n];
List<Integer> cycleSizes = new ArrayList<>(); // 所有节点度数为2的连通分量（环）
List<Integer> pathSizes = new ArrayList<>(); // 其余连通分量（链）
// 遍历每个连通分量
for (int i = 0; i < n; i++) {
if (seen[i]) continue;
List<Integer> component = getComponent(graph, i, seen);
// 判断是否为环：所有节点度数均为2
boolean allDegree2 = true;
for (int u : component) {
if (graph[u].size() != 2) {
allDegree2 = false;
break;
}
}
if (allDegree2) {
cycleSizes.add(component.size());
} else if (component.size() > 1) {
pathSizes.add(component.size());
}
// 孤立点（size==1）不贡献边权，无需处理
}
// 先处理环：从剩余的最大数中分配
for (int cycleSize : cycleSizes) {
ans += calculateScore(n - cycleSize + 1, n, true);
n -= cycleSize;
}
// 链按长度从大到小排序，优先处理长链
Collections.sort(pathSizes, Collections.reverseOrder());
for (int pathSize : pathSizes) {
ans += calculateScore(n - pathSize + 1, n, false);
n -= pathSize;
}
return ans;
}
// BFS/DFS 获取连通分量中的所有节点
private List<Integer> getComponent(List<Integer>[] graph, int start, boolean[] seen) {
List<Integer> component = new ArrayList<>();
Queue<Integer> queue = new LinkedList<>();
queue.offer(start);
seen[start] = true;
component.add(start);
while (!queue.isEmpty()) {
int u = queue.poll();
for (int v : graph[u]) {
if (!seen[v]) {
seen[v] = true;
queue.offer(v);
component.add(v);
}
}
}
return component;
}
/**
* 计算将 [left, right] 范围内的数填入一个连通分量的最大边权和
*
* 填数策略：用双端队列模拟，初始放入两个最大值 right
* 从 right-1 递减到 left，每次取出队列前端与当前值相乘，再将当前值放入队尾
* 这样大数会集中在中间，次大数交替向两边扩展
*
* @param left 可用数的最小值
* @param right 可用数的最大值
* @param isCycle 是否为环（环需要额外加上首尾相连的一条边）
* @return 该连通分量的最大边权和
*/
private long calculateScore(int left, int right, boolean isCycle) {
Deque<Long> deque = new ArrayDeque<>();
deque.offerLast((long) right);
deque.offerLast((long) right);
long score = 0;
for (int value = right - 1; value >= left; value--) {
long windowValue = deque.pollFirst();
score += windowValue * value;
deque.offerLast((long) value);
}
// 如果是环，首尾两个节点也相邻，额外加上它们的乘积
if (isCycle) {
score += deque.peekFirst() * deque.peekLast();
}
return score;
}
}
```
---
关键说明
要点 说明
连通分量分类 所有节点度数均为 2 → 环；否则为链（含孤立点）
处理顺序 环优先于链，因为环的每个节点都有两条边，大数在环中能产生更多乘积；链按长度降序，长链优先拿大数
calculateScore 双端队列模拟"中间放大数，向两边递减"的排列。例如 `[left..right]=[7,8,9,10,11]`，排列为 `9-11-10-8-7`，相邻乘积和最大
环额外处理 环首尾相连，所以 `deque.peekFirst() * deque.peekLast()` 是最后一条边的贡献
> 注意：这道题在赛后被社区发现部分测试数据存在争议（官方答案可能不是最优），但上述贪心策略是标准竞赛解法。