题目描述的链接如下:

得分最高的最小轮调

首先,刚拿到这道题我首先想到的当然是暴力解法,循环每一个$k$,计算得分,然后得分最大的$k$,即为所求,很明显,这种方法,肯定会导致TLE(Time Limit Exceed)。没想到方法的我,自然就是去看官方的题解。

首先,是这个题目的两个关键题眼:

  1. 是怎么轮调的,$n$ 为数组的长度,$k$ 为数组中的一个下标(index),轮调完后,$k$ 到数组的最后一个元素$(k, n-1)$ 这段区间会移动到原数组的最前面,然后就是$k$前面的那一段(顺序不变)$(0,k-1)$,会附加到后面来。
  2. 然后就是记分,任何值小于或等于其索引的项都可以记作一分,也就是说,如果索引值为 $i$ ,然后 $nums[i]=x$ , 当 $x = nums[i] \le i$ 时可以记一分。也可以反过来理解,当索引值大于等于当前值的时候可以记一分,即 $i \ge nums[i] = x$ 记一分。

数组 $nums$ 中的一个元素 $x$ ,只有当 $x$ 所在下标范围为 $[x, n-1]$ 时,才会记一分,当 $x$ 下标为 $[0, x-1]$ 时不记分。

假设元素 $x$ 的当前下标为 $i$ ,如果轮调下标为 $k$ , 那么 $x$ 经过轮调过后的下标就为 $(n-k+i) \bmod n$ (或者写为 $(i-k+n) \bmod n$ ),这里最后为什么要取$n$的模,是防止超过数组范围,而如果元素 $x$ 要记一分,那么它的下标就应该是 $(n-k+i) \bmod n \ge x$ ,等价于 $ (n+i-x) \bmod n \ge k$ ,又因为元素 $x$ 记一分的下标有 $n-x$个,所以说,我们可以得到 $k \ge (i+1) \bmod n$ , 因为 $k$ 的的位置总是被移动到下标为0的地方,$k$ 的前一个值总是被移动到 $n-1$ 的位置,也就是不管怎么算都是符合条件(当前下标值大于等于当前值)的位置。

将取模运算去掉,那么我们就可以得到 $k$ 的实际取值范围(能够记分)。

  • 当 $i < x$ 的时候, $k$ 大于等于 $(i+1)$ 时,慢慢变大时,$x$是从最后一个慢慢往前移的,它肯定不能移动到下标小于$x$的位置,也就是说$k$ 的范围为 $i+1 \le k \le (n-x+i)$
  • 当 $i \ge x$ 的时候,$k$的取值范围可以是大于等于 $(i+1)$,也可以是小于等于 $(i-x)$ (也就当前值可以往前移动的步数,因为当k为0时,不移动时,也是符合条件可以记分的)

每个元素我们都可以通过上面的方法来计算记1分的轮调下表范围,遍历完所有元素之后,就可以得到每个轮调下标(也就是 $k$ )对应的记1分的元素个数,最后就可以得到记1分最多的轮调下标是多少。注意,如果有多个得分最高的轮调下标,则取最小的那个。

一般做法是用一个数组保存轮调下标为 $k$ 时的得分,对于每个元素,我们可以得到该元素记1分的轮调下标范围,将数组中所有这个下标范围的值都加1,然后找到最大元素的最小下标即可,但时间复杂度还是 $O(n^2)$ , 所以我们需要利用差分数组来降低时间复杂度。

根据前面的条件,我们是要将一段或两端连续下标范围内的元素加1,所以我们可以使用差分数组来实现,差分数组就是原来数组 $i$ 位置上的元素和 $i-1$ 位置上的元素作差,然后放到 $i$ 位置上,我们定义原来数组中的-1位置的值为0。

定义长度为 $n$ 的差分数组 $diffs$,首先令 $low = (i+1)\bmod n, high = (n-x+i+1) \bmod n$ ,将$diffs[low]$ 的值加 1,将 $diffs[high]$ 的值减1,如果 $low \ge high$,则将 $diffs[0]$ 的值加 1。(

注意,$low$代表的是第一个符合条件的$k$的下标,我们将 $diffs[low]$ 加1,代表的是,$low$ 下标后面的数都是加了1的,即这个范围的$k$ 的都都可以记1分

$high$代表的是最后一个符合条件的 $k$ 的下一个,即不能够记1分的位置,相当于是 $low$ 开始的那一段记分区间之后,就全部不记分了。减去1就是抵消前面的加1。

当$low \ge high$时,证明存在来两段区间需要加1,一段为$(low, n-1)$,另一段为$(0, high-1)$,这个时候就要将$diff[0]+1$,即原来的保存$k$的数组的第一个值要加1,相当于从0到 $high$ 的这一段都为1。

遍历并更新$diffs$之后,我们需要再遍历一遍数组$diffs$计算前缀和,每个下标处的前缀和即可表示当前轮调下标处的得分,记录最大得分和最大得分的最小下标,遍历结束之后即可得到结果。

C++的代码如下

class Solution{
public:
    int bestRotation(vector<int>& nums){
        int len = nums.size();
        vector<int> diffs(len);
        for (int i = 0; i < len; ++i) {
           int low = (i+1)%len;
           int high = (i-nums[i]+len+1)%len;
           diffs[low]++;
           diffs[high]--;
            if (low >= high){
                diffs[0]++;
            }
        }
        int bestIndex = 0;
        int maxScore = 0;
        int score = 0;
        for (int i = 0; i < len; ++i) {
            score += diffs[i];
            if (score > maxScore){
                bestIndex = i;
                maxScore = score;
            }
        }
        return bestIndex;
    }
};