class Solution {
public:
int bestRotation(vector<int>& nums) {
}
};
798. 得分最高的最小轮调
给你一个数组 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 <= 1050 <= nums[i] < nums.length原站题解
golang 解法, 执行用时: 100 ms, 内存消耗: 8.3 MB, 提交时间: 2023-06-05 14:11:17
func bestRotation(nums []int) int {
n := len(nums)
diffs := make([]int, n)
for i, num := range nums {
low := (i + 1) % n
high := (i - num + n + 1) % n
diffs[low]++
diffs[high]--
if low >= high {
diffs[0]++
}
}
score, maxScore, idx := 0, 0, 0
for i, diff := range diffs {
score += diff
if score > maxScore {
maxScore, idx = score, i
}
}
return idx
}
python3 解法, 执行用时: 244 ms, 内存消耗: 26.7 MB, 提交时间: 2023-06-05 14:10:58
class Solution:
def bestRotation(self, nums: List[int]) -> int:
n = len(nums)
diffs = [0] * n
for i, num in enumerate(nums):
low = (i + 1) % n
high = (i - num + n + 1) % n
diffs[low] += 1
diffs[high] -= 1
if low >= high:
diffs[0] += 1
score, maxScore, idx = 0, 0, 0
for i, diff in enumerate(diffs):
score += diff
if score > maxScore:
maxScore, idx = score, i
return idx
golang 解法, 执行用时: 92 ms, 内存消耗: 8.4 MB, 提交时间: 2023-06-05 14:10:29
func bestRotation(nums []int) (ans int) {
n := len(nums)
diff := make([]int, n + 1)
for i := 0; i < n; i++ {
if num := nums[i]; i >= num {
diff[0]++
diff[i - num + 1]--
diff[i + 1]++
} else {
diff[i + 1]++
diff[i - num + n + 1]--
}
}
for i, cur, max := 0, 0, 0; i < n; i++ {
cur += diff[i]
if cur > max {
ans, max = i, cur
}
}
return
}
javascript 解法, 执行用时: 72 ms, 内存消耗: 51.3 MB, 提交时间: 2023-06-05 14:10:16
/**
* @param {number[]} nums
* @return {number}
*/
var bestRotation = function(nums) {
const n = nums.length
const diff = new Array(n + 1).fill(0)
for(let i = 0; i < n; i++) {
if(i >= nums[i]) {
diff[0]++
diff[i - nums[i] + 1]--
diff[i + 1]++
} else {
diff[i + 1]++
diff[i - nums[i] + n + 1]--
}
}
let ans = 0, cur = 0, max = 0
for(let i = 0; i < n; i++) {
cur += diff[i]
if(cur > max) {
ans = i
max = cur
}
}
return ans
};
java 解法, 执行用时: 4 ms, 内存消耗: 54.4 MB, 提交时间: 2023-06-05 14:10:02
class Solution {
public int bestRotation(int[] nums) {
int n = nums.length;
int[] diff = new int[n + 1];
for(int i = 0; i < n; i++) {
if(i >= nums[i]) {
diff[0]++;
diff[i - nums[i] + 1]--;
diff[i + 1]++;
} else {
diff[i + 1]++;
diff[i - nums[i] + n + 1]--;
}
}
int ans = 0, cur = 0, max = 0;
for(int i = 0; i < n; i++) {
cur += diff[i];
if(cur > max) {
ans = i;
max = cur;
}
}
return ans;
}
}
python3 解法, 执行用时: 244 ms, 内存消耗: 26.8 MB, 提交时间: 2023-06-05 14:09:49
# 差分数组
class Solution:
def bestRotation(self, nums: List[int]) -> int:
n = len(nums)
diff = [0] * (n + 1)
# num ---> n - 1
for i, num in enumerate(nums):
if i >= num:
diff[0] += 1
diff[i - num + 1] -= 1
diff[i + 1] += 1
else:
diff[i + 1] += 1
diff[i - num + n + 1] -= 1
ans = cur = mx = 0
for i in range(n):
cur += diff[i]
if cur > mx:
ans, mx = i, cur
return ans