这个问题是 LeetCode 798 题“得分最高的最小轮调”。目标是找到一个最小的轮调次数 k，使得数组轮调后得分最高。得分定义为：每个元素在轮调后的新位置索引不小于该元素的值。

解题思路

我们考虑每个元素对各个轮调次数 k 的贡献。对于数组中的每个元素 nums[i]（值为 v），经过 k 次左移后，它的新索引为 (i - k + n) % n。该元素得分的条件是 (i - k + n) % n >= v。

通过数学变换，可以得出：对于每个元素，它能得分的 k 集合是一个循环区间 [L, R]，其中：

· L = (i + 1) % n
· R = (i + n - v) % n

注意：如果 v >= n，则该元素永远无法得分，直接忽略。

因此，我们可以用差分数组来统计每个 k 的总得分。对于每个有效元素：

· 如果 L <= R，则在 diff[L] 加 1，diff[R+1] 减 1。
· 如果 L > R，则区间跨越数组末尾，需要拆分成 [L, n-1] 和 [0, R] 两部分：
· diff[L] 加 1，diff[n] 减 1（表示第一段结束）
· diff[0] 加 1，diff[R+1] 减 1

最后，对差分数组求前缀和，得到每个 k 的得分，记录最大得分对应的最小 k。

代码实现

public int bestRotation(int[] nums) {
    int n = nums.length;
    int[] diff = new int[n + 1]; // 差分数组，多一位方便处理边界

    for (int i = 0; i < n; i++) {
        int v = nums[i];
        if (v >= n) continue; // 永远无法得分

        int L = (i + 1) % n;
        int R = (i + n - v) % n;

        if (L <= R) {
            diff[L]++;
            diff[R + 1]--;
        } else {
            // 区间 [L, n-1]
            diff[L]++;
            diff[n]--;
            // 区间 [0, R]
            diff[0]++;
            diff[R + 1]--;
        }
    }

    int maxScore = -1;
    int bestK = 0;
    int curScore = 0;
    for (int k = 0; k < n; k++) {
        curScore += diff[k];
        if (curScore > maxScore) {
            maxScore = curScore;
            bestK = k;
        }
    }
    return bestK;
}

复杂度分析

· 时间复杂度：O(n)，只需遍历数组和差分数组。
· 空间复杂度：O(n)，用于差分数组。

该解法能正确处理所有情况，并返回最小轮调次数。