LeetCode 396. 旋转函数Rotate Function详解从暴力到 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\)中的最大值。题目约束条件n nums\.length1 \lt; n \lt; 10^5\-100 \lt; nums\[i\] \lt; 100答案保证符合 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 最大值 26示例 2输入: nums [100] 输出: 0只有一种旋转方式F\(0\) 0\*100 0因此结果为 0。三、解题思路暴力法直观但不可行3.1 思路原理最直观的解题方式枚举所有旋转位置k0到n\-1每次构建顺时针旋转后的新数组按照题目定义计算当前F\(k\)最终遍历得到所有值的最大值。复杂度缺陷单次计算F\(k\)需要O\(n\)时间总共枚举n次整体时间复杂度为O(n2)O(n^2)O(n2)。当n10^5时计算量高达10^10会直接超时无法通过大数据用例。该方法仅用于理解题目逻辑不适合正式提交。3.2 暴力法完整代码fromtypingimportListclassSolution:defmaxRotateFunction_bruteforce(self,nums:List[int])-int:nlen(nums)max_valfloat(-inf)forkinrange(n):# 构建顺时针旋转 k 次后的数组后k位移到最前ifk0:rotatednumselse:rotatednums[-k:]nums[:-k]# 按定义计算当前 F(k)cur0foriinrange(n):curi*rotated[i]# 更新最大值max_valmax(max_val,cur)returnmax_val# 测试代码if__name____main__:solSolution()print(sol.maxRotateFunction_bruteforce([4,3,2,6]))# 输出 26print(sol.maxRotateFunction_bruteforce([100]))# 输出 0四、数学递推优化O(N) 最优解法4.1 核心公式推导想要通过海量数据测试必须将时间复杂度优化至线性级O(n)O(n)O(n)。核心思路是寻找相邻两次旋转函数的递推关系消除重复计算。设数组长度为n数组所有元素总和为S sum\(nums\)。先列出基础公式F(0)0⋅nums[0]1⋅nums[1]2⋅nums[2]...(n−1)⋅nums[n−1]F(0) 0 \cdot nums[0] 1 \cdot nums[1] 2 \cdot nums[2] ... (n-1) \cdot nums[n-1]F(0)0⋅nums[0]1⋅nums[1]2⋅nums[2]...(n−1)⋅nums[n−1]数组顺时针旋转1次后新数组为\[nums\[n\-1\], nums\[0\], nums\[1\], \.\.\., nums\[n\-2\]\]此时旋转函数为F(1)0⋅nums[n−1]1⋅nums[0]2⋅nums[1]...(n−1)⋅nums[n−2]F(1) 0 \cdot nums[n-1] 1 \cdot nums[0] 2 \cdot nums[1] ... (n-1) \cdot nums[n-2]F(1)0⋅nums[n−1]1⋅nums[0]2⋅nums[1]...(n−1)⋅nums[n−2]4.2 差值分析与公式化简对比F\(0\)和F\(1\)可以发现规律除了被移到首位的末尾元素nums\[n\-1\]其余所有元素的权重系数全部 1而nums\[n\-1\]的权重从n\-1直接降为 0。权重全部1带来的总增量为S \- nums\[n\-1\]末尾元素权重清零带来的总减量为\(n\-1\) \* nums\[n\-1\]合并化简可得F(1)F(0)S−n⋅nums[n−1]F(1) F(0) S - n \cdot nums[n-1]F(1)F(0)S−n⋅nums[n−1]4.3 通用递推公式推广到任意旋转次数k每次旋转都会将当前数组的末尾元素移至首位可得通用递推公式F(k)F(k−1)S−n×nums[n−k]F(k) F(k-1) S - n \times nums[n-k]F(k)F(k−1)S−n×nums[n−k]公式核心解读\S所有元素权重统一1整体总和增加数组总和\- n \* nums\[n\-k\]被移到首位的元素损失了n倍的自身数值是旋转带来的固定差值4.4 图解辅助理解假设原数组nums \[a₀, a₁, a₂, \.\.\., aₙ₋₁\]总和S sum\(nums\)F(0) 0·a₀ 1·a₁ 2·a₂ ... (n-1)·aₙ₋₁ F(1) F(0) S - n·aₙ₋₁ F(2) F(1) S - n·aₙ₋₂ ... F(k) F(k-1) S - n·nums[n-k]五、完整代码实现5.1 标准优化版推荐提交fromtypingimportListclassSolution:defmaxRotateFunction(self,nums:List[int])-int:nlen(nums)# 计算数组元素总和totalsum(nums)# 计算初始旋转函数 F(0)F0fori,numinenumerate(nums):Fi*num# 记录最大值初始为 F(0)max_FF# 递推计算 F(1) ~ F(n-1)forkinrange(1,n):FFtotal-n*nums[n-k]max_Fmax(max_F,F)returnmax_F5.2 Python 简洁写法负数索引优化利用 Python 负数索引特性nums\[\-i\]等价于nums\[n\-i\]代码更简洁优雅fromtypingimportListclassSolution:defmaxRotateFunction(self,nums:List[int])-int:nlen(nums)totalsum(nums)# 列表推导式快速计算 F(0)Fsum(i*numfori,numinenumerate(nums))max_FF# 递推所有旋转结果foriinrange(1,n):FFtotal-n*nums[-i]max_Fmax(max_F,F)returnmax_F5.3 完整测试代码多用例验证fromtypingimportListclassSolution:defmaxRotateFunction(self,nums:List[int])-int:nlen(nums)totalsum(nums)Fsum(i*numfori,numinenumerate(nums))max_FFforiinrange(1,n):FFtotal-n*nums[-i]max_Fmax(max_F,F)returnmax_F# 批量测试用例if__name____main__:solSolution()# 基础示例nums1[4,3,2,6]print(f示例1输出:{sol.maxRotateFunction(nums1)})# 26nums2[100]print(f示例2输出:{sol.maxRotateFunction(nums2)})# 0# 拓展测试用例nums3[1,2,3,4,5,6,7,8,9,10]print(f测试用例3输出:{sol.maxRotateFunction(nums3)})# 330nums4[-2,0,5,-1,2]print(f测试用例4输出:{sol.maxRotateFunction(nums4)})# 16六、复杂度分析解题方法时间复杂度空间复杂度是否可AC暴力模拟法O(n2)O(n^2)O(n2)O(n)O(n)O(n)否超时数学递推优化法O(n)O(n)O(n)O(1)O(1)O(1)是最优解优化解法详解时间计算数组总和、初始F\(0\)、递推遍历均为单次线性遍历总复杂度O(n)O(n)O(n)空间仅使用常数临时变量未开辟额外数组原地计算空间复杂度O(1)O(1)O(1)七、核心要点总结核心递推公式F(k)F(k−1)sum(nums)−n×nums[n−k]F(k) F(k-1) sum(nums) - n \times nums[n-k]F(k)F(k−1)sum(nums)−n×nums[n−k]是解题的关键旋转本质顺时针旋转一次 末尾元素移至首位其余元素权重1边界自适应当数组长度n1时递推循环不会执行直接返回F\(0\)0无需额外判断数值兼容公式支持数组正负元素无需特殊处理适配题目所有数据范围优化思想算法常见优化思路通过状态递推剔除重复计算将平方级复杂度降为线性级八、拓展思考若题目改为逆时针旋转递推公式需要如何调整若权重不再是0、1、2\.\.\.n\-1的连续递增序列该递推优化思路是否仍然适用此类旋转带权求和题型核心逻辑均为挖掘相邻操作的状态差值用数学公式替代暴力模拟是算法刷题的经典优化模型。