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 。

示例

示例一：

输入：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，得分最高。

示例二：

输入：nums = [1,3,0,2,4]
输出：0
解释：
nums 无论怎么变化总是有 3 分。
所以我们将选择最小的 k，即 0。

提示

  • $1 <= nums.length <= 10^5$
  • $0 <= nums[i] < nums.length$

解题

当数字下标大于值时得分。

对于给定的 nums[i]，能使得其得分的下标区间是明确的。基本上是位于右半边能得分，位于左半边不得分。

这意味着，能使其得分的「 k 区间 」也是明确的。只要计算出，在 k 从 0 到 n-1 的过程中，什么时候从得分变成失分，什么时候从失分变成得分。

  • 如果一开始就在得分圈，那么随着 k 的增加，（元素逐渐左移），会先失分，然后在轮回后得分，直到最后
    • 一开始得分，此时的次数为 0
    • 随着下标变小，对于某个nums[i]<=i的数字而言，左移到下标为nums[i]的时候，仍然还可以得分；再多移动一格则不可得分，此时的次数为 i - nums[i] + 1
    • 轮回后会一直得分，此时的次数为 i+1
  • 如果一开始在失分圈，那么随着 k 的增加，会在大轮回后得分，然后进入失分圈，直到最后
    • 从0开始到下标i的每个位置都不可得分
    • 下标为num[i]-i时，不得分，此时的次数为 n - (nums[i] - i) + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
int[] diff = new int[n];
for(int i=0; i<n; i++){
  if (nums[i]<=i){
    // 在得分圈
    diff[0]++;	// 不移动时 nums[i] 就产生贡献
    diff[(i-nums[i]+1)%n]--;	// 左移 i-nums[i]+1 是，首次变为正，贡献取消
    diff[(i+1)%n]++;	// 直到移动到坐标小于 0 的位置，变成移动到最右边，贡献产生
  } else {
    // 在失分圈
    diff[(i+1)%n]++;	// 移动到最右边，贡献产生
    diff[(n-(nums[i]-i)+1)%n]--;	// 值和下标相同的临界点，继续左移则贡献取消
  }
}

整体思路就是遍历一遍每个数，通过直接计算得到产生分数贡献变化的分界点，将对应的移动值和变化记录下来。最后求总分的时候再遍历累计求和即可；相当于用积分恢复差分对应的原始值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public int bestRotation(int[] nums){
  int ans = 0;
  int n = nums.length;
  int[] diff = new int[n];
  for (int i = 0; i < n; i++) {
    if (nums[i]<=i){
      // nums[i] 初始位置可以得分
      diff[0]++; // 不移动时 nums[i】就产生贡献
      diff[(i-nums[i]+1)%n]--; // 左移 i-nums[i]+1 则差首次为正，贡献取消，继续左移也不会产生新贡献
      diff[(i+1)%n]++; // 直到移动到坐标小于0的位置，变成移动到最右边，贡献产生
    }else {
      // 一开始所在的位置不得分，左移没有用，只有移动到边界才会产生变化
      diff[(i+1)%n]++;
      // 继续向左移动，则会再次到达值和下标相同的临界点，继续左移一位则得分取消
      diff[(n-(nums[i]-i)+1)%n]--;
    }
  }
  int score = 0;
  int max = 0;
  for (int m = 0; m<n; m++){
    score+=diff[m];
    if (score>max){
      max = score;
      ans = m;
    }
  }
  return ans;
}