给你一个数组 nums，我们可以将它按一个非负整数 k 进行轮调，这样可以使数组变为 [nums[k], nums[k + 1], … nums[nums.length - 1], nums[0], nums[1], …, nums[k-1]] 的形式。此后，任何值小于或等于其索引的项都可以记作一分。
例如，数组为 nums = [2,4,1,3,0]，我们按 k = 2 进行轮调后，它将变成 [1,3,0,2,4]。这将记为 3 分，因为 1 > 0 [不计分]、3 > 1 [不计分]、0 <= 2 [计 1 分]、2 <= 3 [计 1 分]，4 <= 4 [计 1 分]。
在所有可能的轮调中，返回我们所能得到的最高分数对应的轮调下标 k 。如果有多个答案，返回满足条件的最小的下标 k 。
示例 1：
输入：nums = [2,3,1,4,0]
输出：3
解释：
下面列出了每个 k 的得分：
k = 0, nums = [2,3,1,4,0], score 2
k = 1, nums = [3,1,4,0,2], score 3
k = 2, nums = [1,4,0,2,3], score 3
k = 3, nums = [4,0,2,3,1], score 4
k = 4, nums = [0,2,3,1,4], score 3
所以我们应当选择 k = 3，得分最高。
示例 2：
输入：nums = [1,3,0,2,4]
输出：0
解释：
nums 无论怎么变化总是有 3 分。
所以我们将选择最小的 k，即 0。
提示：
1 <= nums.length <= 105
0 <= nums[i] < nums.length
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/smallest-rotation-with-highest-score
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路：
本题可以转换思路去想，可以转成判断nums[i]在哪个位置进行反转是是符合条件的，然后将对应反转的位置贡献值+1，这样最后判断每个反转位置的贡献值即可。本来想用线段树维护区间和，然后发现直接用差分数组，在起点+1，结束位置的后面位置-1就可以，也更简单。
示例1中i=2时nums[2]=1。根据样例可以发现，k=0~1 以及 k=3-4都是符合条件的，所以sum数组就要在这些位置+1。
代码
class Solution {
public:
int sum[100010]={0};
int bestRotation(vector<int>& nums) {
int n=nums.size();
for(int i=0;i<nums.size();i++){
if(nums[i]<=i){
sum[0]++;sum[i-nums[i]+1]--;
sum[i+1]++;sum[n]--;
}
else{
sum[i+1]++;sum[(n-(nums[i]-i))+1]--;
}
}
for(int i=1;i<nums.size();i++){
sum[i]+=sum[i-1];
}
int mx=0,idx;
for(int i=0;i<nums.size();i++){
if(mx<sum[i]){
mx=max(mx,sum[i]);idx=i;
}
}
return idx;
}
};