差分数组

发表于 更新于 分类于 Waline：

这周的每日一题有一道困难级别的题目，使用了一种叫做差分数组的技巧，这个技巧其实也不复杂，就是前缀和的反向操作，简单记录一下。

这是题目的链接：https://leetcode-cn.com/problems/smallest-rotation-with-highest-score/

这个题目最简单的做法就是遍历每个可能的k，然后计算当前数组的得分，最后比较那个情况下得分是最大的，如果有多个最大的，那么取k值小的。

但是这样一来，算法的复杂度就是n的平方级别的。

所以我们需要找出其中的规律，然后对这个规律加以简化。

首先，我们分析下这个问题：设，下标为i的数字为x，那么根据题目条件，我们可以知道，当x<=i时，该元素计一分。

所以说，元素x计一分的数组下标范围为[x, n-1]。

如果我们轮调次数为k，那么轮调之后，因为是向左轮调，轮调之后的下标为(i - k + n) mod n

所以说，(i - k + n) mod n的范围应该为[x, n - 1]

运算一下可以得到，k <= (i - x + n) mod n, k >= (i + 1) mod n。

去掉取模运算后，当i < x 时，i + 1 <= k <= i - x + n，当 i >= x时，k >= i + 1 或 k <= i - x

对于数组 nums 中的每个元素，都可以根据元素值与元素所在下标计算该元素记 1 分的轮调下标范围。遍历所有元素之后，即可得到每个轮调下标对应的计 1 分的元素个数，计 1 分的元素个数最多的轮调下标即为得分最高的轮调下标。如果存在多个得分最高的轮调下标，则取其中最小的轮调下标。

创建长度为 n 的数组 points，其中 points[k] 表示轮调下标为 k 时的得分。对于数组 nums 中的每个元素，得到该元素记 1 分的轮调下标范围，然后将数组 points 的该下标范围内的所有元素加 1。当数组 points 中的元素值确定后，找到最大元素的最小下标。该做法的时间复杂度仍然是 O(n^2)，为了降低时间复杂度，需要利用差分数组。

假设元素 x 的初始下标为 i。当 i < x 时应将 points 的下标范围 [i + 1, i - x + n] 内的所有元素加 1，当 i≥x 时应将 points 的下标范围 [0, i - x] 和 [i + 1, n - 1] 内的所有元素加 1。由于是将一段或两段连续下标范围内的元素加 1，因此可以使用差分数组实现。定义长度为 n 的差分数组 diffs，其中 diffs[k]=points[k]−points[k−1]（特别地，points[−1]=0），具体做法是：令low=(i+1) mod n，high=(i−x+n+1) mod n，将 diffs[low] 的值加 1，将 diffs[high] 的值减 1，如果low≥high 则将 diffs[0] 的值加 1。

遍历数组 nums 的所有元素并更新差分数组之后，遍历数组 diffs 并计算前缀和，则每个下标处的前缀和表示当前轮调下标处的得分。在遍历过程中维护最大得分和最大得分的最小轮调下标，遍历结束之后即可得到结果。

下面是C语言版本的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int bestRotation(int* nums, int numsSize){
    int* diffs = (int*)malloc(sizeof(int) * numsSize);
    memset(diffs, 0, sizeof(int) * numsSize);
    for(int i = 0; i < numsSize; i++) {
        int low = (i + 1) % numsSize;
        int high = (i - nums[i] + numsSize + 1) % numsSize;
        diffs[low]++;
        diffs[high]--;
        if (low >= high) {
            diffs[0]++;
        }
    }
    int bestIndex = 0, maxScore = 0, score = 0;
    for(int i = 0; i < numsSize; i++) {
        score += diffs[i];
        if (maxScore < score) {
            bestIndex = i;
            maxScore = score;
        }
    }
    free(diffs);
    return bestIndex;
}