2022-11-16：给你一个数组 nums，我们可以将它按一个非负整数 k 进行轮调，例如，数组为 nums = [2,4,1,3,0]，我们按 k = 2 进行轮调后，它将变成 [1,3,0,

2022-11-16
北京
本文字数：1096 字
阅读完需：约 4 分钟

2022-11-16：给你一个数组 nums，我们可以将它按一个非负整数 k 进行轮调，例如，数组为 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。

答案 2022-11-16：

力扣 798。差分数组。时间复杂度：O(N)。空间复杂度：O(N)。代码用 rust 编写。代码如下：

use std::iter::repeat;
impl Solution {    pub fn best_rotation(nums: Vec<i32>) -> i32 {        let n = nums.len() as i32;        // cnt : 差分数组        // cnt最后进行前缀和的加工！        // 加工完了的cnt[0] :  整体向右移动0的距离, 一共能得多少分        // 加工完了的cnt[i] :  整体向右移动i的距离, 一共能得多少分        let mut cnt: Vec<i32> = repeat(0).take((n + 1) as usize).collect();        for i in 0..n {            // 遍历每个数！            // 看看每个数，对差分数组哪些范围，会产生影响!            if nums[i as usize] < n {                if i <= nums[i as usize] {                    Solution::add(&mut cnt, nums[i as usize] - i, n - i - 1);                } else {                    Solution::add(&mut cnt, 0, n - i - 1);                    Solution::add(&mut cnt, n - i + nums[i as usize], n - 1);                }            }        }        for i in 1..=n {            cnt[i as usize] += cnt[(i - 1) as usize];        }        // 最大得分是啥！已经求出来了        let mut max = cnt[0];        let mut ans = 0;        let mut i = n - 1;        while i >= 1 {            // 整体移动的i 0 n-1 n-2 n-3 1            //         k 0  1   2   3   n-1            if cnt[i as usize] > max {                max = cnt[i as usize];                ans = i;            }            i -= 1;        }        return if ans == 0 { 0 } else { n - ans };    }    fn add(cnt: &mut Vec<i32>, l: i32, r: i32) {        cnt[l as usize] += 1;        cnt[(r + 1) as usize] -= 1;    }}
fn main() {    let nums = vec![2, 3, 1, 4, 0];    let ans = Solution::best_rotation(nums);    println!("ans = {:?}", ans);}
struct Solution {}