396.旋转函数：求diff（增量法）

【LetMeFly】396.旋转函数：求diff（增量法）

力扣题目链接：https://leetcode.cn/problems/rotate-function/

给定一个长度为 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 <= 105
• -100 <= nums[i] <= 100

解题方法：增量法

以样例1为例：

$nums = [4, 3, 2, 6]$

$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(0)$得到$F(1)$呢？很简单：

$F(1) = F(0) + (4 + 3 + 2 + 6) - 4\times 6$

即：$F(1)=F(0)+\sum nums[i] - len(nums)\times nums[-1]$

我们只需要遍历一遍$nums$数组，得到$F(0)$、$\sum nums[i]$，就能在$O(1)$的时间内推出$F(1)$了，递推推到$F(n-1)$总耗时$O(n)$。

• 时间复杂度$O(n)$
• 空间复杂度$O(1)$

AC代码

C++

/*
 * @LastEditTime: 2026-05-01 21:34:50
 */
typedef long long ll;
class Solution {
public:
    int maxRotateFunction(vector<int>& nums) {
        ll now = 0, sum = 0;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            now += i * nums[i];
            sum += nums[i];
        }
        
        ll ans = now;
        for (int i = 1; i < n; i++) {
            now = now + sum - n * nums[n - i];
            ans = max(ans, now);
        }
        return ans;
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源