LeetCode 补拙笔记

0. 前言

• 日期：2026.05.20
• 题目：396. 旋转函数
• 难度：中等
• 标签：数组、数学、前缀和

1. 题目理解

问题描述： 给定一个长度为 n 的整数数组 nums，把数组向右旋转 k 次后，计算旋转函数 F(k) = 0 * nums[0] + 1 * nums[1] + ... + (n-1) * nums[n-1]。 求所有 F(0), F(1), ..., F(n-1) 中的最大值。

示例：

输入：nums = [4,3,2,6] 输出：26

2. 解题思路

核心观察

• 暴力计算每一轮旋转后的结果会超时 $O(n^2)$。
• 找到递推公式：
  • $F(k)=F(k-1)+sum(nums)-n\ast nums[n-k]$
• 用递推公式 $O(n)$ 直接算出所有结果。

算法步骤

1. 计算初始值 $F(0)$ 和数组总和 $sum$。
2. 利用递推公式依次计算 $F(1),F(2)...$。
3. 记录过程中的最大值。

3. 代码实现

class Solution {
    public int maxRotateFunction(int[] nums) {
        int n = nums.length;
        int[] arr = new int[n];
        int sum = 0;
        int res = 0;
        for (int i = 0; i < n; i++) {
            res += (i * nums[i]);
            sum += nums[i];
        }
        arr[0] = res;
        for (int i = 1; i < n; i++) {
            arr[i] = arr[i - 1] + sum - (n * nums[n - i]);
            res = Math.max(res,arr[i]);
        }

        return res;
    }
}

4. 代码优化说明

去掉多余数组，原地更新，减少空间使用，无多余判断：

class Solution {
public int maxRotateFunction(int[] nums) {
int n = nums.length;
int curSum = 0;
int s = 0;
for(int i = 0;i < n;i++){
curSum += i * nums[i];
s += nums[i];
}
int ans = curSum;
for(int i = n - 1;i >= 0;i--){
curSum += s;
curSum -= nums[i] * n;
ans = Math.max(ans,curSum);
}
return ans;
}
}

5. 复杂度分析

• 时间复杂度：$O(n)$ 两次线性遍历。
• 空间复杂度：$O(1)$ 仅用常数变量，无额外数组。

6. 总结

• 核心：数学递推公式，避免暴力旋转。
• 公式：$F(k)=F(k-1)+sum-n\ast last$
• 优化后空间从 $O(n)$ 降到 $O(1)$，效率更高。