M396.旋转函数

math, 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 <= 10^5
-100 <= nums[i] <= 100

这是一个经典的数组题目，核心在于通过数学推导找到 $F (k)$ 与 $F (k - 1)$ 之间的递推关系，从而将时间复杂度从 $O (n^{2})$ 降低到 $O (n)$ 。

数学推导

假设数组为 nums，长度为 $n$ ，数组所有元素的和为 $S = \sum_{i = 0}^{n - 1} n u m s [i]$ 。

根据定义：

$F (0) = 0 \cdot n u m s [0] + 1 \cdot n u m s [1] + \dots + (n - 2) \cdot n u m s [n - 2] + (n - 1) \cdot n u m s [n - 1]$
$F (1)$ 是顺时针旋转 1 位后的结果，即数组变为 $[n u m s [n - 1], n u m s [0], n u m s [1], \dots, n u m s [n - 2]]$ ： $F (1) = 0 \cdot n u m s [n - 1] + 1 \cdot n u m s [0] + 2 \cdot n u m s [1] + \dots + (n - 1) \cdot n u m s [n - 2]$

我们计算 $F (1) - F (0)$ ： $F (1) - F (0) = (n u m s [0] + n u m s [1] + \dots + n u m s [n - 2]) - (n - 1) \cdot n u m s [n - 1]$

利用总和 $S$ 代换： $n u m s [0] + n u m s [1] + \dots + n u m s [n - 2] = S - n u m s [n - 1]$

所以： $F (1) - F (0) = (S - n u m s [n - 1]) - (n - 1) \cdot n u m s [n - 1]$ $F (1) - F (0) = S - n \cdot n u m s [n - 1]$ 即 $F (1) = F (0) + S - n \cdot n u m s [n - 1]$

推广到一般情况： $F (k) = F (k - 1) + S - n \cdot n u m s [n - k]$

算法步骤

计算数组所有元素的和 S。
计算初始函数值 F(0)。
利用递推公式 $F (k) = F (k - 1) + S - n \cdot n u m s [n - k]$ 依次计算 $F (1)$ 到 $F (n - 1)$ 。
在计算过程中维护并返回最大值。

Python 代码实现

python

class Solution:
    def maxRotateFunction(self, nums: List[int]) -> int:
        n = len(nums)
        # 1. 计算数组总和 S
        s = sum(nums)
        
        # 2. 计算初始的 F(0)
        # f 代表当前的 F(k)，初始为 F(0)
        f = sum(i * num for i, num in enumerate(nums))
        
        res = f
        
        # 3. 迭代计算 F(1) 到 F(n-1)
        # 根据推导：F(k) = F(k-1) + S - n * nums[n-k]
        for k in range(1, n):
            f = f + s - n * nums[n - k]
            if f > res:
                res = f
                
        return res

复杂度分析

时间复杂度： $O (n)$ 。我们需要遍历数组一次计算 S 和 F(0)，然后再遍历一次计算 $F (k)$ 。
空间复杂度： $O (1)$ 。只使用了常数级别的额外空间。

M396.旋转函数 ​

M396.旋转函数