396. 旋转函数

1. 题目简介

难度：中等，原题链接：396. 旋转函数。

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

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

• F(k) = 0 * arrk[0] + 1 * arrk[1] + ... + (n - 1) * arrk[n - 1]

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

生成的测试用例让答案符合 32 位 整数。

2. 问题分析

相邻两次旋转只改变了各元素的下标，可以从上一次的加权和推导下一次结果，无需真的移动数组。

2.1 相邻旋转的递推关系

题目按向右旋转定义 F(k)，下面的推导和代码按向左旋转枚举。两个方向都会遍历全部 n 种排列，只是顺序不同，因此求出的最大值相同。为对应下面的公式，这一节用 F(i) 表示向左旋转 i 位后的加权和，arr 表示原数组。

向左旋转一位时，原来的第一个元素移到末尾，其权重从 0 变成 n - 1；其余元素的权重都减 1：

F(0) = 0 * arr[0] + 1 * arr[1] + ... + (n - 1) * arr[n - 1]
F(1) = (n - 1) * arr[0] + 0 * arr[1] + ... + (n - 2) * arr[n - 1]

可以先把所有元素的权重都减 1，也就是从结果中减去 sum(arr)。但 arr[0] 的权重应该变成 n - 1，而不是 -1，所以再补上 n * arr[0]：

F(1) - F(0) = n * arr[0] - sum(arr)

左移 i 次之后，位于开头的元素是原数组中的 arr[i]。于是得到递推式：

F(i + 1) = F(i) + n * arr[i] - sum(arr)

2.2 记录当前值与最大值

先遍历数组，求出初始加权和 walk 与元素总和 sum。再用递推式计算其余 n - 1 种旋转结果，每算出一个 walk，就更新最大值 ans。这一步只需要读取原数组中依次移到末尾的元素。

3. 代码实现

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

4. 复杂度分析

• 时间复杂度：O(n)，需要遍历数组。
• 空间复杂度：O(1)。

来源：Coding 101 原文 · 免费阅读，引用请保留出处。内容使用说明