396. 旋转函数
396. 旋转函数
题目
You are given an integer array nums of length n.
Assume arrk to be an array obtained by rotating nums by k positions clock-wise. We define the rotation function F on nums as follow:
F(k) = 0 * arrk[0] + 1 * arrk[1] + ... + (n - 1) * arrk[n - 1].
Return the maximum value of F(0), F(1), ..., F(n-1).
The test cases are generated so that the answer fits in a 32-bit integer.
Example 1:
Input: nums = [4,3,2,6]
Output: 26
Explanation:
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 = 26So the maximum value of F(0), F(1), F(2), F(3) is F(3) = 26.
Example 2:
Input: nums = [100]
Output: 0
Constraints:
n == nums.length1 <= n <= 10^5-100 <= nums[i] <= 100
题目大意
给定一个长度为 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 位 整数。
示例 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.length1 <= n <= 10^5-100 <= nums[i] <= 100
解题思路
- 观察旋转变化规律
题目要求我们找到数组 nums 所有旋转状态下的最大旋转函数值 F(k)，其中
F(k) = [k, k+1...n-2,n-1,0,....k-1] * nums
可以通过数学公式推导得出：
F(k + 1) = [k+1,k+2...n-1,0, 1,.....k] * nums
观察旋转变化规律：
F(k + 1) = F(k) + sum - n * nums[n - 1 - k]
- 初始化
- 数组长度为
n - 计算数组元素和为
sum = nums[0] + nums[1] + ... + nums[n - 1] - 初始旋转函数值
rotation = 0 * nums[0] + 1 * nums[1] + ... + (n - 1) * nums[n - 1] - 初始旋转函数最大值
maxRotation = rotation
- 遍历求最大值
遍历 k = 1 到 n - 1，根据公式递推计算 F(k) 并更新最大值。
- 返回最大值
返回旋转函数最大值 maxRotation。
复杂度分析
- 时间复杂度：
O(n)，遍历一次数组计算sum和F(0)，再用O(n)计算每次旋转函数值。 - 空间复杂度：
O(1)，只需常数空间存储中间变量。
代码
/**
* @param {number[]} nums
* @return {number}
*/
var maxRotateFunction = function (nums) {
const n = nums.length;
const sum = nums.reduce((acc, cur) => acc + cur, 0);
let rotation = nums.reduce((acc, cur, i) => acc + cur * i, 0);
let maxRotation = rotation;
for (let i = 1; i < n; i++) {
rotation = rotation + sum - n * nums[n - i];
maxRotation = Math.max(maxRotation, rotation);
}
return maxRotation;
};