这道题是 LeetCode 3266和 3264 的区别在于 k 的范围扩大到 1e9直接堆模拟会超时需要用数学规律优化。核心思路当数组中 所有元素都大于当前最大值 时后续操作会进入稳定循环每次操作选择最小的元素乘完后它变成最大n 次操作正好轮完一轮。因此分两阶段处理1. 模拟阶段用最小堆模拟直到堆顶元素 × multiplier 当前最大值或 k 用完2. 批量阶段剩余操作均匀分配到每个元素用快速幂计算Java 实现javaclass 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;// 最小堆[值, 索引]PriorityQueuelong[] 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 后超过 maxValwhile (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^baseint 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 的情况。