文章目录
题目
标题和出处
标题：得分最高的最小轮调
难度
8 级
题目描述
要求
给定一个数组 nums \texttt{nums} nums，我们可以将它按一个非负整数 k \texttt{k} k 进行轮调，这样可以使数组变为 nums[k], nums[k + 1], nums[k + 2], … , nums[nums.length - 1], nums[0], nums[1], … , nums[k - 1] \texttt{nums[k], nums[k + 1], nums[k + 2], \ldots, nums[nums.length - 1], nums[0], nums[1], \ldots, nums[k - 1]} nums[k], nums[k + 1], nums[k + 2], …, nums[nums.length - 1], nums[0], nums[1], …, nums[k - 1] 的形式。此后，任何值小于或等于其索引的项都可以计 1 \texttt{1} 1 分。
- 例如，如果数组为 [2, 4, 1, 3, 0] \texttt{[2, 4, 1, 3, 0]} [2, 4, 1, 3, 0]，我们按 k = 2 \texttt{k = 2} k = 2 进行轮调后，它将变成 [1, 3, 0, 2, 4] \texttt{[1, 3, 0, 2, 4]} [1, 3, 0, 2, 4]。这将计 3 \texttt{3} 3 分，因为 1 > 0 \texttt{1} > \texttt{0} 1>0（ 0 \texttt{0} 0 分）， 3 > 1 \texttt{3} > \texttt{1} 3>1（ 0 \texttt{0} 0 分）， 0 ≤ 2 \texttt{0} \le \texttt{2} 0≤2（ 1 \texttt{1} 1 分）， 2 ≤ 3 \texttt{2} \le \texttt{3} 2≤3（ 1 \texttt{1} 1 分）， 4 ≤ 4 \texttt{4} \le \texttt{4} 4≤4（ 1 \texttt{1} 1 分）。
在所有可能的轮调中，返回我们所能得到的最高分数对应的轮调索引 k \texttt{k} k。如果有多个答案，返回满足条件的最小的索引 k \texttt{k} k。
示例
示例 1：
输入：
[2,
3,
1,
4,
0]
\texttt{[2, 3, 1, 4, 0]}
[2, 3, 1, 4, 0]
输出：
3
\texttt{3}
3
解释：
下面列出了每个
k
\texttt{k}
k 的得分：
k
=
0
\texttt{k = 0}
k = 0，
nums
=
[2,3,1,4,0]
\texttt{nums = [2,3,1,4,0]}
nums = [2,3,1,4,0]，
2
\texttt{2}
2 分
k
=
1
\texttt{k = 1}
k = 1，
nums
=
[3,1,4,0,2]
\texttt{nums = [3,1,4,0,2]}
nums = [3,1,4,0,2]，
3
\texttt{3}
3 分
k
=
2
\texttt{k = 2}
k = 2，
nums
=
[1,4,0,2,3]
\texttt{nums = [1,4,0,2,3]}
nums = [1,4,0,2,3]，
3
\texttt{3}
3 分
k
=
3
\texttt{k = 3}
k = 3，
nums
=
[4,0,2,3,1]
\texttt{nums = [4,0,2,3,1]}
nums = [4,0,2,3,1]，
4
\texttt{4}
4 分
k
=
4
\texttt{k = 4}
k = 4，
nums
=
[0,2,3,1,4]
\texttt{nums = [0,2,3,1,4]}
nums = [0,2,3,1,4]，
3
\texttt{3}
3 分
所以我们应当选择
k
=
3
\texttt{k = 3}
k = 3，得分最高。
示例 2：
输入：
[1,
3,
0,
2,
4]
\texttt{[1, 3, 0, 2, 4]}
[1, 3, 0, 2, 4]
输出：
0
\texttt{0}
0
解释：
nums
\texttt{nums}
nums 无论怎么变化总是有
3
\texttt{3}
3 分。所以我们将选择最小的
k
\texttt{k}
k，即
0
\texttt{0}
0。
数据范围
- 1 ≤ nums.length ≤ 10 5 \texttt{1} \le \texttt{nums.length} \le \texttt{10}^\texttt{5} 1≤nums.length≤105
- 0 ≤ nums[i] < nums.length \texttt{0} \le \texttt{nums[i]} < \texttt{nums.length} 0≤nums[i]<nums.length
解法
思路和算法
最直观的做法是对所有可能的轮调分别计算得分，记录最高得分和最高得分对应的轮调索引。当数组 nums \textit{nums} nums 的长度为 n n n 时，共有 n n n 种可能的轮调，对于每种轮调计算得分需要 O ( n ) O(n) O(n) 的时间，因此总时间复杂度为 O ( n 2 ) O(n^2) O(n2)，会超出时间限制，因此必须优化。
对于数组 nums \textit{nums} nums 中的元素 x x x，只有当 x x x 的索引大于或等于 x x x 时， x x x 才会计 1 1 1 分，因此 x x x 的索引在 [ x , n − 1 ] [x, n-1] [x,n−1] 范围内时会计 1 1 1 分，该范围的长度为 n − x n-x n−x，即有 n − x n-x n−x 个轮调使得 x x x 计 1 1 1 分，其余 x x x 个轮调使得 x x x 不计分。
如果初始时， x x x 位于索引 i i i，即 nums [ i ] = x \textit{nums}[i]=x nums[i]=x，则当轮调索引为 k k k 时， x x x 将位于索引 ( i − k + n ) m o d n (i-k+n) \bmod n (i−k+n)modn。当 ( i − k + n ) m o d n ≥ x (i-k+n) \bmod n \ge x (i−k+n)modn≥x 时， x x x 将会计 1 1 1 分。
将上述不等式进行转换可以得到：当 x x x 计 1 1 1 分时，轮调索引 k k k 应满足 k ≤ ( i − x + n ) m o d n k \le (i-x+n) \bmod n k≤(i−x+n)modn。又由于使得 x x x 计 1 1 1 分的 k k k 有 n − x n-x n−x 个取值，因此当 x x x 计 1 1 1 分时，有 k ≥ ( i + 1 ) m o d n k \ge (i+1) \bmod n k≥(i+1)modn。
由于上述 k k k 的表示有取余运算，因此 k k k 的实际取值范围由 x x x、 i i i 和 n n n 决定：
-
当 i < x i<x i<x 时， i + 1 ≤ k ≤ i + n − x i+1 \le k \le i+n-x i+1≤k≤i+n−x；
-
当 i ≥ x i \ge x i≥x 时， k ≥ i + 1 k \ge i+1 k≥i+1 或 k ≤ i − x k \le i-x k≤i−x。
对于数组 nums \textit{nums} nums 中的任意元素 x x x，都可以得到 x x x 计 1 1 1 分的轮调索引范围。只要找到数组 nums \textit{nums} nums 中的每一个元素对应的计 1 1 1 分的轮调索引范围，然后在所有轮调索引中找到计 1 1 1 分的次数最多的轮调索引，即为得分最高的轮调索引。如果存在多个得分最高的轮调索引，则取其中的最小轮调索引。
创建长度为 n n n 的数组 points \textit{points} points，其中 points [ k ] \textit{points}[k] points[k] 表示轮调索引为 k k k 时的得分。为了优化时间复杂度，可以使用差分数组的做法计算 points \textit{points} points 的每个元素值，具体做法如下：
-
遍历数组 nums \textit{nums} nums，对于 nums [ i ] = x \textit{nums}[i]=x nums[i]=x，令 low = ( i + 1 ) m o d n \textit{low}=(i+1) \bmod n low=(i+1)modn， high = ( i + n − x + 1 ) m o d n \textit{high}=(i+n-x+1) \bmod n high=(i+n−x+1)modn，然后将 points [ low ] \textit{points}[\textit{low}] points[low] 的值加 1 1 1，将 points [ high ] \textit{points}[\textit{high}] points[high] 的值减 1 1 1，如果 low > high \textit{low}>\textit{high} low>high，则再将 points [ 0 ] \textit{points}[0] points[0] 的值加 1 1 1；
-
维护最高得分和最高得分下标，初始值都是 0 0 0，遍历数组 points \textit{points} points 并计算其前缀和，使用前缀和更新最高得分和最高得分下标。遍历结束时即可得到最高得分，此时的最高得分下标即为得分最高的最小轮调索引。
上述差分数组的做法的正确性说明如下：
-
对于数组 nums \textit{nums} nums 中的任意元素 x x x，如果 x x x 计 1 1 1 分的轮调索引范围是连续的，则该范围是 [ i + 1 , i + n − x ] [i+1, i+n-x] [i+1,i+n−x]，等价于 [ low , high − 1 ] [\textit{low},\textit{high}-1] [low,high−1]，将 points [ low ] \textit{points}[\textit{low}] points[low] 的值加 1 1 1，将 points [ high ] \textit{points}[\textit{high}] points[high] 的值减 1 1 1，然后更新前缀和，该范围内的得分都会加 1 1 1；
-
对于数组 nums \textit{nums} nums 中的任意元素 x x x，如果 x x x 计 1 1 1 分的轮调索引范围是不连续的，则该范围是 [ 0 , i − x ] ∪ [ i + 1 , n − 1 ] [0, i-x] \cup [i+1, n-1] [0,i−x]∪[i+1,n−1]，等价于 [ 0 , high − 1 ] ∪ [ low , n − 1 ] [0, \textit{high}-1] \cup [\textit{low}, n-1] [0,high−1]∪[low,n−1]，将 points [ 0 ] \textit{points}[0] points[0] 和 points [ low ] \textit{points}[\textit{low}] points[low] 的值分别加 1 1 1，将 points [ high ] \textit{points}[\textit{high}] points[high] 的值减 1 1 1，然后更新前缀和，该范围内的得分都会加 1 1 1。
代码
class Solution {
public int bestRotation(int[] nums) {
int length = nums.length;
int[] points = new int[length];
for (int i = 0; i < length; i++) {
int low = (i + 1) % length;
int high = (i + length - nums[i] + 1) % length;
points[low]++;
points[high]--;
if (low > high) {
points[0]++;
}
}
int maxIndex = 0;
int maxScore = 0;
int curScore = 0;
for (int i = 0; i < length; i++) {
curScore += points[i];
if (curScore > maxScore) {
maxIndex = i;
maxScore = curScore;
}
}
return maxIndex;
}
}
复杂度分析
-
时间复杂度： O ( n ) O(n) O(n)，其中 n n n 是数组 nums \textit{nums} nums 的长度。整个过程需要遍历数组 nums \textit{nums} nums 两次。
-
空间复杂度： O ( n ) O(n) O(n)，其中 n n n 是数组 nums \textit{nums} nums 的长度。需要创建一个长度为 n n n 的数组 points \textit{points} points。