原文链接: https://leetcode-cn.com/problems/smallest-rotation-with-highest-score
英文原文
You are given an array nums. You can rotate it by a non-negative integer k so that the array becomes [nums[k], nums[k + 1], ... nums[nums.length - 1], nums[0], nums[1], ..., nums[k-1]]. Afterward, any entries that are less than or equal to their index are worth one point.
- For example, if we have
nums = [2,4,1,3,0], and we rotate byk = 2, it becomes[1,3,0,2,4]. This is worth3points because1 > 0[no points],3 > 1[no points],0 <= 2[one point],2 <= 3[one point],4 <= 4[one point].
Return the rotation index k that corresponds to the highest score we can achieve if we rotated nums by it. If there are multiple answers, return the smallest such index k.
Example 1:
Input: nums = [2,3,1,4,0] Output: 3 Explanation: Scores for each k are listed below: 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 So we should choose k = 3, which has the highest score.
Example 2:
Input: nums = [1,3,0,2,4] Output: 0 Explanation: nums will always have 3 points no matter how it shifts. So we will choose the smallest k, which is 0.
Constraints:
1 <= nums.length <= 1050 <= nums[i] < nums.length
中文题目
给定一个数组 A，我们可以将它按一个非负整数 K 进行轮调，这样可以使数组变为 A[K], A[K+1], A{K+2], ... A[A.length - 1], A[0], A[1], ..., A[K-1] 的形式。此后，任何值小于或等于其索引的项都可以记作一分。
例如，如果数组为 [2, 4, 1, 3, 0]，我们按 K = 2 进行轮调后，它将变成 [1, 3, 0, 2, 4]。这将记作 3 分，因为 1 > 0 [no points], 3 > 1 [no points], 0 <= 2 [one point], 2 <= 3 [one point], 4 <= 4 [one point]。
在所有可能的轮调中，返回我们所能得到的最高分数对应的轮调索引 K。如果有多个答案，返回满足条件的最小的索引 K。
示例 1：
输入：[2, 3, 1, 4, 0] 输出：3 解释： 下面列出了每个 K 的得分： K = 0, A = [2,3,1,4,0], score 2 K = 1, A = [3,1,4,0,2], score 3 K = 2, A = [1,4,0,2,3], score 3 K = 3, A = [4,0,2,3,1], score 4 K = 4, A = [0,2,3,1,4], score 3 所以我们应当选择 K = 3，得分最高。
示例 2：
输入：[1, 3, 0, 2, 4] 输出：0 解释： A 无论怎么变化总是有 3 分。 所以我们将选择最小的 K，即 0。
提示：
A的长度最大为20000。A[i]的取值范围是[0, A.length]。
通过代码
官方题解
区间覆盖：
分析
我们首先来看对于数组 A 中的每一个数，它在什么情况下会贡献一分。假设数组的长度 N = 10，A[2] = 5，那么当轮调 0, 1, 2, 8, 9 次时，5 会出现在数组的第 2, 1, 0, 4, 3 的位置，此时 5 不会贡献一分。在其它的轮调中，5 会贡献一分。我们称不会贡献一分的那些位置为 “坏位置”。
对于任意一个数，它对应的 “坏位置” 的下标一定是连续的。并且由于在每一次轮调中，我们相当于把所有的数往左移动了一位，那么这些 “坏位置” 对应的轮调次数应当也是连续的，但根据这个数初始的位置，这个连续区间可能会被拆分成两个。例如在上面的例子中，轮调 0, 1, 2, 8, 9 次可以看成 10, 11, 12, 8, 9 次，此时是一个 [8 .. 12] 的连续区间，但因为 5 初始就在坏位置，因此实际上被拆分成了 [0, 1, 2] 和 [8, 9] 两个区间。
我们可以用这种方法求出数组 A 中每一个数的 “坏位置” 对应的区间。如果某一个轮调位置被 k 个区间覆盖，那么它对应的分数就为 N - k。因此我们只需要找到被最少区间覆盖的那个位置即可。
算法
首先对于数组 A 中的每一个元素 A[i]，我们可以知道，轮调次数在 i - A[i] + 1 和 i 之间时，它不会贡献一分。其中 i - A[i] + 1 和 i 都是在对 N 取模的意义下的。
如果 A[i] 对应的是一个连续的区间，例如 [2, 3, 4]，那我们可以将 bad[2] 的值增加 1，并将 bad[5] 的值减少 1，通过这种方法转换成差分的形式。如果 A[i] 对应的是两个区间，例如 [8, 9, 0, 1, 2]，那我们可以将 bad[10] 和 bad[3] 的值增加 1，并将 bad[8] 和 bad[0] 的值减少 1。注意到轮调次数只会是 0 - 9，因此 bad[10] 增加 1 的操作可以忽略。
在这之后，对于第 i 次轮调，就有 -(bad[0] + ... + bad[i]) 个区间覆盖了它，这样我们就可以在线性时间内找出最优解了。
[sol1]class Solution { public int bestRotation(int[] A) { int N = A.length; int[] bad = new int[N]; for (int i = 0; i < N; ++i) { int left = (i - A[i] + 1 + N) % N; int right = (i + 1) % N; bad[left]--; bad[right]++; if (left > right) bad[0]--; } int best = -N; int ans = 0, cur = 0; for (int i = 0; i < N; ++i) { cur += bad[i]; if (cur > best) { best = cur; ans = i; } } return ans; } }
[sol1]class Solution(object): def bestRotation(self, A): N = len(A) bad = [0] * N for i, x in enumerate(A): left, right = (i - x + 1) % N, (i + 1) % N bad[left] -= 1 bad[right] += 1 if left > right: bad[0] -= 1 best = -N ans = cur = 0 for i, score in enumerate(bad): cur += score if cur > best: best = cur ans = i return ans
复杂度分析
时间复杂度：$O(N)$，其中 $N$ 是数组
A的长度。空间复杂度：$O(N)$。
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 1483 | 3163 | 46.9% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
