1 题目：得分最高的最小轮调

官方标定难度：难

给你一个数组 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 <= $10^5$
0 <= nums[i] < nums.length

2 solution

本题直接做复杂度太大，需要转换一下思路，对于每一个 num 都有一个连续的得分位置, 比如说数字 5 的得分位置就是 [5, n - 1]。依据这一点我们可以知道每一个数轮转多少次才可以到达自己的得分范围，这也是一个连续的范围——典型的差分思想，标记好开始和结束位置，最终求前缀和即可。

代码

class Solution {
public:
int bestRotation(vector<int> &nums) {int n = nums.size();vector<int> range(n + 1);for (int i = 0; i < n; i++) {// 最终在 [nums[i] , n - 1] 可以得分// 移动 i - nums[i], i - (n - 1) 次int r = (i - nums[i] + n) % n, l = (i - (n - 1) + n) % n;// cout << l << r << endl;if (l > r) {range[l]++;range[n]--;range[0]++;range[r + 1]--;} else {range[l]++;range[r + 1]--;}}int Max_index = 0;for (int i = 1; i < n; i++) {range[i] += range[i - 1];//cout << range[i];if (range[i] > range[Max_index])Max_index = i;}return Max_index;
}
};

结果