Leetcode 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 <= 10^5
• 0 <= nums[i] < nums.length

思路

首先的思路当然是暴力求解，直接遍历K在0到nums.length这个范围内的所有得分，然后取得分最高的k值（若有多个取较小的k）即可，这样写思路很清晰代码也是比较简单的，但是这道题目的数据量是$10^5$，这样做的时间复杂度是$O(N^2)$，肯定是会超时的，所以需要去优化。

首先我们将问题转化，先求出数组中每个值要取得得分时k的范围，假设下标为i，则需要：

$nums_i \leq (i-k+n)\%n \\ 0 \leq (i-k+n)\%n \leq n-1 \\ \Downarrow \\ k \leq (i-nums_i+n)\\%n \\ k \leq (i+n)\%n \\ k \geq (i+1)\%n$

最终得到k的范围为：

$k \in \left\{ \begin{aligned} &\lbrack(i+1)\%n,(i-nums_i+n)\%n\rbrack && (i+1)\%n \leq (i-nums_i+n)\%n \\ &\lbrack0,(i-nums_i+n)\%n\rbrack \cup \lbrack(i+1)\%n, n-1\rbrack && (i+1)\%n > (i-nums_i+n)\%n \\ \end{aligned} \right.$

我们就可以在$O(n)$的时间内求得每项可以得分的k的区间，这样问题就转换为了求k取多少时落在这些区间里最多（k取较小值）？

然后我们可以这样来求解：先初始化一个长度为n，值为0的数组，然后对于上述的每个区间，将这个数组下标落在区间里的值加一，遍历完之后值最大的那个下标即为得分最高的k值。但是这样做的时间复杂度依然为$O(n^2)$，因为有n+个区间，每个区间的长度的数量级也为n，所以这里需要引入一个算法：差分数组

差分数组

差分数组就是专门对数组的某个区间进行相同的操作，且时间复杂度为$O(1)$的一个算法，他的本质其实是前缀和的逆操作。步骤如下：

首先求对应数组的差分数组：

$a_1,a_2,...a_{n-1},a_n \Rightarrow 0,a_2-a_1,a_3-a_2-a_1,...,a_n-a_{n-1}-a_{n-2}-...-a_1$

就本题来说初始的数组是$[0;n]$，那对应的差分数组仍为$[0;n]$；当我们需要对某个区间进行操作时只需要对端点处进行修改，如对$[a,b]$都+1则只需要

$nums_a+=1 \\ nums_{b+1}-=1$

即对左侧端点进行这个修改，对右侧的右边一个进行逆修改。

然后是差分数组如何还原，进行前缀和运算就行了，因为前缀和是对数组前i项的累加，对左侧端点的修改就影响了后面的所有值，而对右侧端点的右边一个逆修改相当于消除了对之后的影响，于是就变成了对$[a,b]$的操作，且这里所有的操作都是$O(1)$的。

然后使用这种算法再对上面的先初始化一个长度为n，值为0的数组，然后对于上述的每个区间，将这个数组下标落在区间里的值加一，遍历完之后值最大的那个下标即为得分最高的k值问题求解就很简单了。

代码

impl Solution {
    pub fn best_rotation(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut diff = vec![0; n+1];
        for i in 0..nums.len() {
            let left = (i+1)%n;
            let right = (i-(nums[i] as usize)+n)%n;
            diff[left]+=1;
            diff[right+1]-=1;
            if left > right {
                diff[0]+=1;
                diff[n]-=1;
            }
        }
        let mut ans = 0;
        let mut tmp = 0;
        let mut sum = 0;
        for k in 0..n {
            sum += diff[k];
            if sum > tmp {
                tmp = sum;
                ans = k;
            }
        }
        ans as i32
    }
}