DeepSeek LeetCode 3266. K 次乘运算后的最终数组 II Java实现

这道题是 LeetCode 3266，和 3264 的区别在于 k 的范围扩大到 1e9，直接堆模拟会超时，需要用数学规律优化。

核心思路

当数组中 所有元素都大于当前最大值 时，后续操作会进入稳定循环：每次操作选择最小的元素，乘完后它变成最大，n 次操作正好轮完一轮。

因此分两阶段处理：

1. 模拟阶段：用最小堆模拟，直到堆顶元素 × multiplier > 当前最大值或 k 用完
2. 批量阶段：剩余操作均匀分配到每个元素，用快速幂计算

Java 实现

```java
class Solution {
private static final int MOD = 1_000_000_007;

public int[] getFinalState(int[] nums, int k, int multiplier) {
int n = nums.length;

// multiplier = 1 时数组不变
if (multiplier == 1) return nums;

// 最小堆：[值, 索引]
PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) ->
a[0] != b[0] ? Long.compare(a[0], b[0]) : Long.compare(a[1], b[1])
);

int maxVal = 0;
for (int i = 0; i < n; i++) {
maxVal = Math.max(maxVal, nums[i]);
pq.offer(new long[]{nums[i], i});
}

// 阶段1：模拟直到堆顶乘 multiplier 后超过 maxVal
while (k > 0 && pq.peek()[0] < maxVal) {
long[] cur = pq.poll();
cur[0] *= multiplier;
pq.offer(cur);
k--;
}

// 阶段2：剩余操作均匀分配
// 此时堆中元素已有序，取出排序
long[][] arr = new long[n][2];
for (int i = 0; i < n; i++) {
arr[i] = pq.poll();
}
// 按值排序（值相同时按索引）
Arrays.sort(arr, (a, b) -> a[0] != b[0] ? Long.compare(a[0], b[0]) : Long.compare(a[1], b[1]));

int base = k / n; // 每个元素至少乘 multiplier^base
int extra = k % n; // 前 extra 个元素多乘一次

int[] result = new int[n];
for (int i = 0; i < n; i++) {
long val = arr[i][0] % MOD;
int idx = (int) arr[i][1];
int exp = base + (i < extra ? 1 : 0);
result[idx] = (int) (val * fastPow(multiplier, exp) % MOD);
}

return result;
}

// 快速幂
private long fastPow(long x, int n) {
long res = 1;
while (n > 0) {
if ((n & 1) == 1) {
res = res * x % MOD;
}
x = x * x % MOD;
n >>= 1;
}
return res;
}
}
```

复杂度分析

· 时间复杂度：O(n log n)
· 堆化 O(n)
· 模拟阶段最多 O(n) 次堆操作
· 排序 O(n log n)
· 空间复杂度：O(n)

示例验证

```java
// 示例
int[] nums = {2, 1, 3, 5, 6};
int k = 5, multiplier = 2;
// 输出: [8, 4, 6, 5, 6]
```

这个解法利用了数学规律将 O(k) 的模拟优化为 O(n log n)，可以高效处理 k 高达 1e9 的情况。