LeetCode中等题之旋转函数

题目

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

解题思路

  题目的做法比较易懂，按照示例1的意思就是下标不动数组每个元素右移或者元素不动，下标左移，我们任取一种固定另外一种就可以完成题目的要求。

class Solution:
    def maxRotateFunction(self, nums: List[int]) -> int:
        index=deque([i for i in range(len(nums))]) #旋转下标
        MAX=-float('inf')
        for i in range(len(nums)):
            s=0
            for j in range(len(nums)):
                s+=nums[j]*index[j]
            if s>MAX:
                MAX=s
            index.append(index.popleft()) #下标左移
        return MAX

  很明显每次都计算全部的数组和其下标，复杂度是O(n^2)所以非常容易超时，因此我们需要利用数学上的方法使得计算量减少，没有思路的话可以在纸上写写划划，当我们将F(0),F(1)的表达式写出来的时候就会发现，这其实就是高中前n项和常用的手段，高斯当年计算的精华错位相减。

class Solution:
    def maxRotateFunction(self, nums: List[int]) -> int:
        s,MAX,S,k=0,-float('inf'),sum(nums),1
        for i,j in enumerate(nums):
            s+=i*j
        for i in range(len(nums)):
            if s>MAX:
                MAX=s
            s+=S-len(nums)*nums[-k]
            k+=1
        return MAX