差分数组知识

查分数组有点类似前缀和的逆运算。假设原数组是num，那么差分数组中，diff[i] = num[i] - num[i - 1]；其中注意的是diff[0] = num[0] - 0。

差分数组主要用于数组频繁进行区间修改的场景。如果在数组的[L, R] 区间增加一个数x，那么只需要在差分数组中

diff[L] += x;
diff[R + 1] -= x;

当然如果R是最后一个元素就不需要再减了。

修改完成后，通过 num[m] = num[m - 1] + diff[m]，就可以依次求出原数组的值。

题目描述

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 。

解题思路

首先可以明确，轮调最少有0轮，最多有数组长度减一轮。我们创建一个轮调数组，保存每轮的得分。

我们可以通过当前数组中每个元素的索引和值计算出它能够在第几轮论调中加分。这样我们就根据每个元素调整轮调数组某个区间的得分。由于需要频繁进行区间修改，就要使用差分数组了。

最后还原成原本数组，看那个分高即为最终答案。

Java代码

class Solution {
    public int bestRotation(int[] nums) {
        // 差分数组
        int[] diffs = new int[nums.length];
        int k = nums.length - 1;
        // 依次计算得分，这里比较复杂，要考虑索引和值的大小关系
        for(int i = 0; i < nums.length; i++) {
            if(i >= nums[i]) {
                diffs[0]++;
                if(i - nums[i] +1 <= k) {
                    diffs[i - nums[i] + 1]--;
                }
                if(i + 1 <= k) {
                    diffs[i + 1]++; 
                }              
            } else {
                diffs[i + 1]++;
                if(i + 1 + k - nums[i] + 1 <= k) {
                    diffs[i + 1 + k - nums[i] + 1 ]--;
                }
                
            }
        }

        // 还原数组，并找出最大值
        int r = 0;
        int index = 0;
        int m = 0;
        for(int i = 0; i <= k; i++) {
            m += diffs[i];
            if(m > r) {
                r = m;
                index = i;
            }
        }
        return index;
    }
}