Kimi LeetCode LCP 24. 数字游戏 Java实现
以下是 LeetCode LCP 24. 数字游戏的 Java 实现，核心思路是转换 + 中位数贪心 + 对顶堆：
```java
class Solution {
private static final int MOD = 1_000_000_007;
public int[] numsGame(int[] nums) {
int n = nums.length;
int[] ans = new int[n];
// 转换：令 a[i] = nums[i] - i
// 这样"nums[a]+1 == nums[a+1]"就等价于"a[a] == a[a+1]"
// 问题转化为：让前i个数相等的最小操作次数（绝对值之和最小化）
// 根据中位数贪心，当所有数等于中位数时，绝对值之和最小
// 大根堆：存储较小的一半，堆顶是较小一半的最大值
PriorityQueue<Long> left = new PriorityQueue<>((a, b) -> Long.compare(b, a));
// 小根堆：存储较大的一半，堆顶是较大一半的最小值（即中位数）
PriorityQueue<Long> right = new PriorityQueue<>();
long sumLeft = 0; // 左堆元素之和
long sumRight = 0; // 右堆元素之和
for (int i = 0; i < n; i++) {
long x = (long) nums[i] - i;
// 插入元素
if (right.isEmpty() || x >= right.peek()) {
right.offer(x);
sumRight += x;
} else {
left.offer(x);
sumLeft += x;
}
// 平衡两个堆的大小，保证 |left.size() - right.size()| <= 1
// 且 right.size() >= left.size()（中位数在右堆顶）
if (right.size() > left.size() + 1) {
long val = right.poll();
sumRight -= val;
left.offer(val);
sumLeft += val;
} else if (left.size() > right.size()) {
long val = left.poll();
sumLeft -= val;
right.offer(val);
sumRight += val;
}
long median = right.peek();
// 计算操作次数 = |所有元素到中位数的距离之和|
// = (median * left.size() - sumLeft) + (sumRight - median * right.size())
long cost = (median * left.size() - sumLeft)
+ (sumRight - median * right.size());
ans[i] = (int) (cost % MOD);
}
return ans;
}
}
```
核心思路
1. 问题转换
题目要求将 `nums[0..i]` 操作成满足 `nums[a]+1 == nums[a+1]` 的序列。这意味着最终序列形如 `x, x+1, x+2, ..., x+i`。
将每个元素减去其下标：`a[i] = nums[i] - i`，则条件转化为 `a[0] == a[1] == ... == a[i]`。
问题变为：让前 i 个数相等的最小操作次数（每次操作可以将某个数 +1 或 -1）。
2. 中位数贪心
对于一维数轴上的点，使所有点到某点的距离之和最小，该点即为中位数。因此目标值应取 `a[0..i]` 的中位数。
3. 对顶堆维护中位数
- 左堆（大根堆）：存储较小的一半
- 右堆（小根堆）：存储较大的一半，堆顶即为中位数
- 维护 `right.size() >= left.size()`，使得中位数始终在右堆顶
每次插入新元素后，通过调整堆的大小保持平衡，然后利用两个堆的元素和快速计算到中位数的距离之和。
复杂度
- 时间复杂度：O(N \log N)，每次堆操作 O(\log N)
- 空间复杂度：O(N)，两个堆的空间
示例验证
以 `nums = [3,4,5,1,6,7]` 为例：
- 转换后：`a = [3, 3, 3, -2, 2, 2]`
- i=0: [3] → 中位数 3，cost=0
- i=1: [3,3] → 中位数 3，cost=0
- i=2: [3,3,3] → 中位数 3，cost=0
- i=3: [3,3,3,-2] → 中位数 3，cost=|3-3|+|3-3|+|3-3|+|-2-3|=5
- i=4: 中位数 3，cost=5+1=6（-2 变 3 需 5 步，2 变 3 需 1 步）
- i=5: 中位数 3，cost=6+1=7
输出 `[0,0,0,5,6,7]` ✓