Hard

题目描述

给定一个数组 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],    得分 2
k = 1,  nums = [3,1,4,0,2],    得分 3
k = 2,  nums = [1,4,0,2,3],    得分 3
k = 3,  nums = [4,0,2,3,1],    得分 4
k = 4,  nums = [0,2,3,1,4],    得分 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

解题思路

解题思路

这是一道需要巧妙运用差分数组的题目。暴力解法时间复杂度为 O(n²)，会超时，需要优化。

核心观察： 对于每个元素 nums[i]，我们需要找出在哪些旋转位置 k 下，该元素能够得分（即 nums[i] <= 新位置）。

分析元素得分条件：

  • 原位置为 i 的元素，旋转 k 位置后的新位置为 (i - k + n) % n
  • 得分条件：nums[i] <= (i - k + n) % n

关键洞察： 每个元素在某个 k 值区间内能得分，在区间外不得分。我们需要找到每个元素的"失分区间"，然后用差分数组统计。

具体步骤：

  1. 对每个元素 nums[i]，计算它在什么情况下不能得分
  2. 不能得分的条件：nums[i] > (i - k + n) % n
  3. 通过数学推导，元素 nums[i] 在区间 [(i - nums[i] + 1 + n) % n, i] 内旋转时会失分
  4. 使用差分数组记录每个旋转位置的得分变化
  5. 找到得分最高且 k 最小的位置

差分数组优化： 通过差分数组，我们可以在 O(1) 时间内更新区间，总时间复杂度降为 O(n)。

代码实现

class Solution {
public:
    int bestRotation(vector<int>& nums) {
        int n = nums.size();
        vector<int> change(n, 0);
        
        for (int i = 0; i < n; i++) {
            // 计算元素nums[i]在位置i时不能得分的旋转区间
            int left = (i - nums[i] + 1 + n) % n;
            int right = (i + 1) % n;
            
            // 差分数组标记失分区间
            change[left] -= 1;
            change[right] += 1;
        }
        
        int maxScore = 0, bestK = 0, currentScore = 0;
        
        // 计算每个k位置的得分变化
        for (int k = 0; k < n; k++) {
            currentScore += change[k];
            if (currentScore > maxScore) {
                maxScore = currentScore;
                bestK = k;
            }
        }
        
        return bestK;
    }
};

class Solution:
    def bestRotation(self, nums: List[int]) -> int:
        n = len(nums)
        change = [0] * n
        
        for i in range(n):
            # 计算元素nums[i]在位置i时不能得分的旋转区间
            left = (i - nums[i] + 1 + n) % n
            right = (i + 1) % n
            
            # 差分数组标记失分区间
            change[left] -= 1
            change[right] += 1
        
        max_score = 0
        best_k = 0
        current_score = 0
        
        # 计算每个k位置的得分变化
        for k in range(n):
            current_score += change[k]
            if current_score > max_score:
                max_score = current_score
                best_k = k
        
        return best_k

public class Solution {
    public int BestRotation(int[] nums) {
        int n = nums.Length;
        int[] change = new int[n];
        
        for (int i = 0; i < n; i++) {
            // 计算元素nums[i]在位置i时不能得分的旋转区间
            int left = (i - nums[i] + 1 + n) % n;
            int right = (i + 1) % n;
            
            // 差分数组标记失分区间
            change[left] -= 1;
            change[right] += 1;
        }
        
        int maxScore = 0, bestK = 0, currentScore = 0;
        
        // 计算每个k位置的得分变化
        for (int k = 0; k < n; k++) {
            currentScore += change[k];
            if (currentScore > maxScore) {
                maxScore = currentScore;
                bestK = k;
            }
        }
        
        return bestK;
    }
}

var bestRotation = function(nums) {
    const n = nums.length;
    const change = new Array(n).fill(0);
    
    for (let i = 0; i < n; i++) {
        // 计算元素nums[i]在位置i时不能得分的旋转区间
        const left = (i - nums[i] + 1 + n) % n;
        const right = (i + 1) % n;
        
        // 差分数组标记失分区间
        change[left] -= 1;
        change[right] += 1;
    }
    
    let maxScore = 0, bestK = 0, currentScore = 0;
    
    // 计算每个k位置的得分变化
    for (let k = 0; k < n; k++) {
        currentScore += change[k];
        if (currentScore > maxScore) {
            maxScore = currentScore;
            bestK = k;
        }
    }
    
    return bestK;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)遍历数组两次，每次O(n)
空间复杂度O(n)需要额外的差分数组存储得分变化