Kimi LeetCode 2836. 在传球游戏中最大化函数值 Java实现
这是 LeetCode 2836 的 Java 实现，核心思路是 倍增法（Binary Lifting）。
核心思路
1. 问题建模：`receiver` 构成一个出度为 1 的功能图（每个节点指向一个节点），要求从某个起点出发走 `k` 步，最大化路径上所有节点值之和（包含起点）。
2. 关键约束：`k` 最大可达 `10^10`，无法暴力模拟，必须用 倍增法 在 O(log k) 时间内跳跃。
3. 倍增预处理：
- `next[i][j]`：从节点 `i` 出发，走 `2^j` 步到达的节点
- `sum[i][j]`：从节点 `i` 出发，走 `2^j` 步经过的中间节点值之和（不含起点）
4. 转移方程：
- `next[i][j] = next[next[i][j-1]][j-1]`
- `sum[i][j] = sum[i][j-1] + sum[next[i][j-1]][j-1]`
5. 答案计算：对每个起点，将 `k` 拆分为二进制位，逐位跳跃累加。
Java 实现
```java
class Solution {
public long getMaxFunctionValue(List<Integer> receiver, long k) {
int n = receiver.size();
// k 的二进制位数，即倍增层数
int m = 64 - Long.numberOfLeadingZeros(k);
// next[i][j] = 从节点 i 出发走 2^j 步到达的节点
int[][] next = new int[n][m];
// sum[i][j] = 从节点 i 出发走 2^j 步，路径上所有中间节点值之和（不含起点 i）
long[][] sum = new long[n][m];
// 初始化：2^0 = 1 步
for (int i = 0; i < n; i++) {
next[i][0] = receiver.get(i);
sum[i][0] = receiver.get(i); // 走1步，只到达 receiver[i]
}
// 倍增预处理
for (int j = 1; j < m; j++) {
for (int i = 0; i < n; i++) {
int mid = next[i][j - 1];
next[i][j] = next[mid][j - 1];
sum[i][j] = sum[i][j - 1] + sum[mid][j - 1];
}
}
long ans = 0;
// 枚举每个起点
for (int start = 0; start < n; start++) {
int curr = start;
long total = start; // 包含起点自身的值
// 将 k 拆分为二进制，逐位跳跃
for (int j = 0; j < m; j++) {
if (((k >> j) & 1) == 1) {
total += sum[curr][j];
curr = next[curr][j];
}
}
ans = Math.max(ans, total);
}
return ans;
}
}
```
复杂度分析
指标 复杂度
时间 O(n × log k)，预处理 O(n log k)，枚举起点 O(n log k)
空间 O(n × log k)，两个二维数组
示例说明
示例 1：`receiver = [2,0,1], k = 4`
- `k = 4 = 100₂`，需要 `m = 3` 层
- 从起点 `2` 出发：
- 初始 `total = 2`
- `k` 的第 2 位为 1：走 `2^2 = 4` 步
- `sum[2][2]` = 路径 `2→1→0→2→1` 的中间节点和 = `1+0+2+1 = 4`
- `total = 2 + 4 = 6`，最终到达节点 `1`
- 答案 `f(2) = 6` ✓
示例 2：`receiver = [1,1,1,2,3], k = 3`
- `k = 3 = 11₂`
- 从起点 `4` 出发：
- 初始 `total = 4`
- 第 0 位为 1：走 1 步，`sum[4][0] = 3`，`curr = 3`，`total = 7`
- 第 1 位为 1：走 2 步，`sum[3][1] = 2+1 = 3`，`curr = 1`，`total = 10`
- 答案 `f(4) = 10` ✓
关键点
- sum 的定义：`sum[i][j]` 存储的是走 `2^j` 步过程中经过的所有节点值之和（不含起点），这样最终答案就是 `起点值 + 各段 sum 之和`。