Medium

题目描述

给定一个长度为 n 的整数数组 nums。

假设 arrₖ 是数组 nums 顺时针旋转 k 个位置后的数组，我们定义 nums 的旋转函数 F 为：

F(k) = 0 * arrₖ[0] + 1 * arrₖ[1] + … + (n - 1) * arrₖ[n - 1]

返回 F(0), F(1), …, F(n-1) 中的最大值。

生成的测试用例保证答案符合 32 位整数范围。

示例 1：

输入：nums = [4,3,2,6]
输出：26
解释：
F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26
所以 F(0), F(1), F(2), F(3) 中的最大值是 F(3) = 26。

示例 2：

输入：nums = [100]
输出：0

提示：

  • n == nums.length
  • 1 <= n <= 10⁵
  • -100 <= nums[i] <= 100

解题思路

解题思路

这道题的关键在于找到相邻旋转函数值之间的递推关系，避免暴力计算每个 F(k)。

暴力解法：直接计算每个 F(k) 的值，时间复杂度为 O(n²)。

优化解法：通过数学推导找到递推关系。

设原数组为 [a₀, a₁, a₂, …, aₙ₋₁]，sum 为数组元素总和。

  • F(0) = 0×a₀ + 1×a₁ + 2×a₂ + … + (n-1)×aₙ₋₁
  • F(1) = 0×aₙ₋₁ + 1×a₀ + 2×a₁ + … + (n-1)×aₙ₋₂

通过观察可以发现： F(1) - F(0) = (a₀ + a₁ + … + aₙ₋₂) - (n-1)×aₙ₋₁ = sum - n×aₙ₋₁

一般地，对于 F(k)： F(k) = F(k-1) + sum - n×nums[n-k]

这样我们只需要计算一次 F(0)，然后通过递推关系依次计算其他值，时间复杂度降为 O(n)。

算法步骤：

  1. 计算数组总和 sum 和初始函数值 F(0)
  2. 使用递推关系计算 F(1) 到 F(n-1)
  3. 记录过程中的最大值

代码实现

class Solution {
public:
    int maxRotateFunction(vector<int>& nums) {
        int n = nums.size();
        long long sum = 0, f = 0;
        
        // 计算数组总和和F(0)
        for (int i = 0; i < n; i++) {
            sum += nums[i];
            f += (long long)i * nums[i];
        }
        
        long long maxF = f;
        
        // 使用递推关系计算F(1)到F(n-1)
        for (int k = 1; k < n; k++) {
            f = f + sum - (long long)n * nums[n - k];
            maxF = max(maxF, f);
        }
        
        return (int)maxF;
    }
};

class Solution:
    def maxRotateFunction(self, nums: List[int]) -> int:
        n = len(nums)
        total_sum = sum(nums)
        
        # 计算F(0)
        f = sum(i * num for i, num in enumerate(nums))
        max_f = f
        
        # 使用递推关系计算F(1)到F(n-1)
        for k in range(1, n):
            f = f + total_sum - n * nums[n - k]
            max_f = max(max_f, f)
        
        return max_f

public class Solution {
    public int MaxRotateFunction(int[] nums) {
        int n = nums.Length;
        long sum = 0, f = 0;
        
        // 计算数组总和和F(0)
        for (int i = 0; i < n; i++) {
            sum += nums[i];
            f += (long)i * nums[i];
        }
        
        long maxF = f;
        
        // 使用递推关系计算F(1)到F(n-1)
        for (int k = 1; k < n; k++) {
            f = f + sum - (long)n * nums[n - k];
            maxF = Math.Max(maxF, f);
        }
        
        return (int)maxF;
    }
}

var maxRotateFunction = function(nums) {
    const n = nums.length;
    let sum = 0, f = 0;
    
    // 计算数组总和和F(0)
    for (let i = 0; i < n; i++) {
        sum += nums[i];
        f += i * nums[i];
    }
    
    let maxF = f;
    
    // 使用递推关系计算F(1)到F(n-1)
    for (let k = 1; k < n; k++) {
        f = f + sum - n * nums[n - k];
        maxF = Math.max(maxF, f);
    }
    
    return maxF;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)只需要遍历数组两次，一次计算初始值，一次计算递推值
空间复杂度O(1)只使用了常数个额外变量