题目描述的链接如下：
首先，刚拿到这道题我首先想到的当然是暴力解法，循环每一个$k$，计算得分，然后得分最大的$k$，即为所求，很明显，这种方法，肯定会导致TLE（Time Limit Exceed）。没想到方法的我，自然就是去看官方的题解。
首先，是这个题目的两个关键题眼：
- 是怎么轮调的，$n$ 为数组的长度，$k$ 为数组中的一个下标（index），轮调完后，$k$ 到数组的最后一个元素$(k, n-1)$ 这段区间会移动到原数组的最前面，然后就是$k$前面的那一段（顺序不变）$(0,k-1)$，会附加到后面来。
- 然后就是记分，任何值小于或等于其索引的项都可以记作一分，也就是说，如果索引值为 $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;
}
};