396. 旋转函数

🟠   🔖  数组 数学 动态规划  🔗 力扣 LeetCode

题目

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 = 26

So 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.length
• 1 <= 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.length
• 1 <= n <= 10^5
• -100 <= nums[i] <= 100

解题思路

1. 观察旋转变化规律

题目要求我们找到数组 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]

2. 初始化

• 数组长度为 n
• 计算数组元素和为 sum = nums[0] + nums[1] + ... + nums[n - 1]
• 初始旋转函数值 rotation = 0 * nums[0] + 1 * nums[1] + ... + (n - 1) * nums[n - 1]
• 初始旋转函数最大值 maxRotation = rotation

3. 遍历求最大值

遍历 k = 1 到 n - 1，根据公式递推计算 F(k) 并更新最大值。

4. 返回最大值

返回旋转函数最大值 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;
};