LeetCode 396. 旋转函数

约 4 分钟
文章信息 7 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节 华为
标签
数组 动态规划 数学

题目描述

✅ 396. 旋转函数

image-20260928223933249

image-20260928223933250

题意分析

数组向右旋转 k 次后，用每个元素乘以它的新下标并求和，得到 F(k)。求 F(0) 到 F(n - 1) 的最大值，包含不旋转的情况；旋转 n 次会回到原数组，不必重复计算。

解法：递推公式

核心思路

[!blue]

若每次真的旋转数组并重新求和，总共需要平方级时间。相邻两次旋转中元素不变，只是下标权重发生规律变化，可以从上一轮的加权和直接递推。

设当前末尾元素为 x，数组总和为 sum。向右旋转一次时，除 x 外的元素都向右移动一格，权重加一；可以先给所有元素的权重都加一，使加权和增加 sum。但 x 实际移到下标 0，刚才却把它的权重从 n - 1 加成了 n，还需要减去 n * x。

所以 新加权和 = 旧加权和 + sum - n * x。第 k 次右旋移到开头的元素，在原数组中的下标是 n - k，得到 F(k) = F(k - 1) + sum - n * nums[n - k]。

先扫描一次计算 sum 和 F(0)，之后用 cur 依次保存当前旋转值，用 best 保存已经枚举的最大值。每次更新只做常数次运算，并且准确对应一种新的旋转位置，枚举完 n 种位置就覆盖了所有候选。

解题步骤

  1. 计算数组总和，以及 cur = Σ i * nums[i]。
  2. 用真实的 F(0) 初始化 best，不要默认答案至少为 0。
  3. 枚举 k = 1..n - 1，按递推式更新 cur，再用它更新 best。
  4. 返回 best。长度为 1 时只有权重 0，初始值就是答案。

题目保证最终答案在 32 位整数范围内，但中间加权和不应依赖这个保证。代码用 long 或 int64 保存计算结果，并在乘法之前提升类型，最后再转换返回值。

代码实现

// 旋转一次的递推关系：F(k) = F(k-1) + sum - n * nums[n-k]。
class Solution {
    public int maxRotateFunction(int[] nums) {
        int n = nums.length;
        long sum = 0;
        long cur = 0;

        for (int i = 0; i < n; i++) {
            sum += nums[i];
            cur += (long) i * nums[i];
        }

        long best = cur;

        for (int k = 1; k < n; k++) {
            // 所有权重先加一，再扣掉越过边界项的全部新权重
            cur = cur + sum - (long) n * nums[n - k];

            if (cur > best) {
                best = cur;
            }
        }

        return (int) best;
    }
}

// 旋转一次的递推关系：F(k) = F(k-1) + sum - n * nums[n-k]。
func maxRotateFunction(nums []int) int {
    n := len(nums)
    var sum int64
    var cur int64

    for i, val := range nums {
        sum += int64(val)
        cur += int64(i) * int64(val)
    }

    best := cur

    for k := 1; k < n; k++ {
        // 所有权重先加一，再扣掉越过边界项的全部新权重
        cur = cur + sum - int64(n)*int64(nums[n-k])
        if cur > best {
            best = cur
        }
    }

    return int(best)
}

复杂度分析

  • 时间复杂度：$O(n)$，初始统计与滚动更新各一次。
  • 空间复杂度：$O(1)$，只维护总和、当前值与最大值。

关键点总结

[!green]

  • 总和是全部权重加一的公共变化，减去 n 倍负责修正越过边界的一项。
  • nums[n - k] 来自原数组，计算过程中不需要修改或旋转数组。
  • 中间乘法与加权和使用宽整数。

易错点总结

[!yellow]

  • 最大值初始零，会在全部候选为负时引入不存在答案。
  • 扣减用 n-1，忘了刚才已经给末项多加一份。
  • 比较后才更新，会漏掉最后一次旋转。
  • 先用窄整数相乘、再赋给宽整数，不能避免乘法本身的溢出。

相似题目

题目 难度 关联与区别
798. 得分最高的最小轮调 困难 同样在全部旋转位置中求最优值，原题累计满足位置条件的贡献，本题累计带下标权重的和。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/82792358
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！