旋转函数

标签: 数组 数学 动态规划

难度: Medium

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

Submission

运行时间: 152 ms

内存: 0.0 MB

class Solution:
    def maxRotateFunction(self, A: List[int]) -> int:
        f = 0
        sum = 0
        for i in range(len(A)):
            f+=i*A[i]
            sum = sum+A[i]
        maxVal = f
        n = len(A)
        for i in range(len(A)-1):
            f = f - A[-i-1]*n + sum
            if f>maxVal:
                maxVal = f
        return maxVal

Explain

这个题解使用了数学方法来优化计算过程。首先计算出初始状态 F(0) 的值，同时计算数组元素总和 sum。然后利用旋转函数的规律，每次旋转后，新的 F(k) 可以通过上一个 F(k-1) 来计算，即 F(k) = F(k-1) - A[n-k]*n + sum，其中 n 为数组长度。通过这种方式，可以在常数时间内计算出每次旋转后的 F(k)，最后取其中的最大值即可。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def maxRotateFunction(self, A: List[int]) -> int:
        # 计算初始状态 F(0) 的值
        f = 0
        # 计算数组元素总和 sum
        sum = 0
        for i in range(len(A)):
            f += i * A[i]
            sum = sum + A[i]
        
        maxVal = f
        n = len(A)
        # 迭代计算 F(1) 到 F(n-1)
        for i in range(len(A) - 1):
            # 根据旋转函数的规律，计算当前旋转后的 F(k)
            f = f - A[-i-1] * n + sum
            # 更新最大值 maxVal
            if f > maxVal:
                maxVal = f
        
        return maxVal

Explore

旋转函数的值F(k)可以通过观察数组旋转后元素的位置变化来推导。F(0)是初始状态，即`0*A[0] + 1*A[1] + ... + (n-1)*A[n-1]`。当数组旋转一次时，每个元素的索引增加1（最后一个元素移到数组首位，索引变为0）。因此，F(1)可以表示为`0*A[n-1] + 1*A[0] + 2*A[1] + ... + (n-1)*A[n-2]`。将F(0)转换为F(1)时，除了A[n-1]外的每个元素A[i]的权重都增加了1。因此，F(1) = F(0) + sum - n*A[n-1]。这里，sum是数组的总和，n是数组长度。对于F(k)，每次旋转后，都是前一个状态减去n倍的最后一个元素的值加上数组总和。所以递推公式为F(k) = F(k-1) - A[n-k]*n + sum，其中A[n-k]是在第k次旋转后移动到数组首位的元素。

在Python中，负数索引表示从数组末尾开始倒数。`-i-1`是计算方法中为了方便从数组末尾获取元素的一种技巧。在迭代过程中，i从0开始增加，所以`-1，-2，-3...`等效于从数组末尾开始计数。例如，当i=0时，`-i-1`结果为-1，即数组的最后一个元素，符合旋转数组后最后一个元素成为第一个元素的逻辑。

在代码中更新`f`的值是为了利用之前计算的F(k-1)来高效计算F(k)，这是动态规划的一种体现。每次基于前一个状态F(k-1)，通过简单的数学操作，即减去n倍的最后一个元素的值并加上数组总和，就可以得到新的状态F(k)。这种方法避免了重新计算F(k)的整体成本，从而大大提高了算法的效率。

在算法执行过程中，`maxVal`初始化为F(0)，即旋转函数的初始值。随后，在每次计算新的F(k)后，都会与当前的`maxVal`进行比较，如果F(k)更大，则更新`maxVal`。这个过程确保了在所有计算的F(k)值中，`maxVal`始终保持为遇到的最大值。因此，最终`maxVal`会是所有可能的F(k)值中的最大值。