LeetCode第396题：旋转函数 · 江川个人博客

博客摘要：本文深入解析LeetCode第396题“旋转函数”，这是一道中等难度的数学优化题目。文章通过数学推导找到旋转函数的递推关系，避免暴力计算，实现O(n)时间复杂度的高效解法。详细讲解算法原理、提供三种语言实现，并分析常见错误和优化技巧，适合有一定算法基础的读者学习数学优化和动态规划思想。

题目描述

给定一个长度为 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

题目链接：LeetCode 396. 旋转函数

解题思路

这道题目的关键在于找到不同旋转状态下函数值之间的数学关系，避免暴力计算每个旋转状态。

核心观察

对于数组 [4,3,2,6]：

F(0) = 0*4 + 1*3 + 2*2 + 3*6 = 25
F(1) = 0*6 + 1*4 + 2*3 + 3*2 = 16

通过数学推导可以发现： F(k) = F(k-1) + sum - n * nums[n-k]

其中：

sum 是数组所有元素的和
n 是数组长度
nums[n-k] 是在第k次旋转中从最高位移到最低位的元素

推导过程

以 [4,3,2,6] 为例：

F(0) = 0*4 + 1*3 + 2*2 + 3*6 = 25
F(1) = 0*6 + 1*4 + 2*3 + 3*2

对比发现：从F(0)到F(1)，除了最后一个元素6移到了开头（系数变为0），其他每个元素的系数都增加了1。

因此：F(1) = F(0) + (4+3+2) - 4*6 = F(0) + sum - n*nums[n-1]

算法原理

数学推导

设数组为 nums = [a0, a1, a2, ..., an-1]，数组和为 sum。

初始状态： F(0) = 0*a0 + 1*a1 + 2*a2 + ... + (n-1)*an-1

旋转一次后： F(1) = 0*an-1 + 1*a0 + 2*a1 + ... + (n-1)*an-2

关键发现：

除了 an-1，其他每个元素的系数都增加了1
an-1 的系数从 (n-1) 变为了 0

因此：

F(1) = F(0) + (a0 + a1 + ... + an-2) - (n-1)*an-1
     = F(0) + sum - an-1 - (n-1)*an-1
     = F(0) + sum - n*an-1

递推公式： F(k) = F(k-1) + sum - n * nums[n-k]

复杂度分析

时间复杂度：O(n)
- 计算数组和：O(n)
- 计算所有旋转函数值：O(n)
- 总时间复杂度：O(n)
空间复杂度：O(1)
- 只使用常数个额外变量
- 不需要额外的数组存储

图解思路

原数组: [4, 3, 2, 6]
数组和: sum = 4 + 3 + 2 + 6 = 15

F(0) = 0*4 + 1*3 + 2*2 + 3*6 = 25
       ↓
F(1) = F(0) + sum - n*nums[3]
     = 25 + 15 - 4*6 = 16
       ↓
F(2) = F(1) + sum - n*nums[2]
     = 16 + 15 - 4*2 = 23
       ↓
F(3) = F(2) + sum - n*nums[1]
     = 23 + 15 - 4*3 = 26

最大值 = max(25, 16, 23, 26) = 26

状态转换过程

旋转次数	当前数组	计算公式	函数值
k=0	[4,3,2,6]	直接计算F(0)	25
k=1	[6,4,3,2]	F(0) + sum - n×nums[3]	16
k=2	[2,6,4,3]	F(1) + sum - n×nums[2]	23
k=3	[3,2,6,4]	F(2) + sum - n×nums[1]	26

代码实现

C# 实现

public class Solution {
    public int MaxRotateFunction(int[] nums) {
        int n = nums.Length;
        
        // 计算数组和与初始F(0)
        int sum = 0;
        int f0 = 0;
        for (int i = 0; i < n; i++) {
            sum += nums[i];           // 数组总和
            f0 += i * nums[i];        // F(0)的值
        }
        
        int maxValue = f0;            // 记录最大值
        int currentF = f0;            // 当前F(k)的值
        
        // 计算F(1), F(2), ..., F(n-1)
        for (int k = 1; k < n; k++) {
            // F(k) = F(k-1) + sum - n * nums[n-k]
            currentF = currentF + sum - n * nums[n - k];
            maxValue = Math.Max(maxValue, currentF);
        }
        
        return maxValue;
    }
}

Python 实现

class Solution:
    def maxRotateFunction(self, nums: List[int]) -> int:
        n = len(nums)
        
        # 计算数组和与初始F(0)
        total_sum = sum(nums)
        f0 = sum(i * nums[i] for i in range(n))
        
        max_value = f0           # 记录最大值
        current_f = f0           # 当前F(k)的值
        
        # 计算F(1), F(2), ..., F(n-1)
        for k in range(1, n):
            # F(k) = F(k-1) + sum - n * nums[n-k]
            current_f = current_f + total_sum - n * nums[n - k]
            max_value = max(max_value, current_f)
        
        return max_value

C++ 实现

class Solution {
public:
    int maxRotateFunction(vector<int>& nums) {
        int n = nums.size();
        
        // 计算数组和与初始F(0)
        long long sum = 0;
        long long f0 = 0;
        for (int i = 0; i < n; i++) {
            sum += nums[i];           // 数组总和
            f0 += (long long)i * nums[i];    // F(0)的值
        }
        
        long long maxValue = f0;      // 记录最大值
        long long currentF = f0;      // 当前F(k)的值
        
        // 计算F(1), F(2), ..., F(n-1)
        for (int k = 1; k < n; k++) {
            // F(k) = F(k-1) + sum - n * nums[n-k]
            currentF = currentF + sum - (long long)n * nums[n - k];
            maxValue = max(maxValue, currentF);
        }
        
        return (int)maxValue;
    }
};

执行结果

C# 实现

执行用时：186 ms
内存消耗：51.2 MB

Python 实现

执行用时：421 ms
内存消耗：25.8 MB

C++ 实现

执行用时：132 ms
内存消耗：28.1 MB

性能对比

语言	执行用时	内存消耗	特点
C++	132 ms	28.1 MB	性能最优，需要注意整数溢出
C#	186 ms	51.2 MB	语法简洁，内存占用较高
Python	421 ms	25.8 MB	代码最简洁，但执行较慢

代码亮点

🎯 数学推导优化：通过递推关系将O(n²)暴力解法优化为O(n)
💡 空间复杂度优化：只使用常数空间，不需要存储所有旋转状态
🔍 溢出处理：C++实现中使用long long防止整数溢出
🎨 代码结构清晰：先计算初始值，再用递推公式更新

常见错误分析

🚫 暴力计算所有旋转状态：时间复杂度O(n²)，会超时
🚫 忽略整数溢出：在计算过程中可能产生大数，需要使用long long
🚫 递推公式理解错误：混淆nums[n-k]的含义，导致计算错误
🚫 边界条件处理不当：没有正确处理单元素数组的情况

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
暴力法	O(n²)	O(1)	思路简单直观	时间复杂度高，大数据超时
数学递推	O(n)	O(1)	时间空间都最优	需要数学推导，理解难度高
记忆化递归	O(n)	O(n)	思路相对清晰	空间复杂度高

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第396题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

👍 点个赞，让更多人看到这篇文章
📁 收藏文章，方便后续查阅复习
🔔 关注作者，获取更多高质量算法题解
💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！

题目描述

解题思路

核心观察

推导过程

算法原理

数学推导

复杂度分析

图解思路

状态转换过程

代码实现

C# 实现

Python 实现

C++ 实现

执行结果

C# 实现

Python 实现

C++ 实现

性能对比

代码亮点

常见错误分析

解法对比

相关题目

📖 系列导航

💬 互动交流