DeepSeek LeetCode 798.得分最高的最小轮调 public int bestRotation(int[] nums)

这个问题是 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] 加 1diff[R1] 减 1。· 如果 L R则区间跨越数组末尾需要拆分成 [L, n-1] 和 [0, R] 两部分· diff[L] 加 1diff[n] 减 1表示第一段结束· diff[0] 加 1diff[R1] 减 1最后对差分数组求前缀和得到每个 k 的得分记录最大得分对应的最小 k。代码实现publicintbestRotation(int[]nums){intnnums.length;int[]diffnewint[n1];// 差分数组多一位方便处理边界for(inti0;in;i){intvnums[i];if(vn)continue;// 永远无法得分intL(i1)%n;intR(in-v)%n;if(LR){diff[L];diff[R1]--;}else{// 区间 [L, n-1]diff[L];diff[n]--;// 区间 [0, R]diff[0];diff[R1]--;}}intmaxScore-1;intbestK0;intcurScore0;for(intk0;kn;k){curScorediff[k];if(curScoremaxScore){maxScorecurScore;bestKk;}}returnbestK;}复杂度分析· 时间复杂度O(n)只需遍历数组和差分数组。· 空间复杂度O(n)用于差分数组。该解法能正确处理所有情况并返回最小轮调次数。