LeetCode 396. 旋转函数

Categories:

题目描述
思路分析
1. 解法一：递推公式（推荐）
相似题目

题目描述

✅ 396. 旋转函数

思路分析

解法一：递推公式（推荐）

核心思路：

先计算 F(0) = sum(i * nums[i]) 和数组总和 sum。

旋转一次的递推关系：F(k) = F(k-1) + sum - n * nums[n-k]。

依次更新并取最大值即可。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(1)。

class Solution {
    public int maxRotateFunction(int[] nums) {
        int n = nums.length;
        long sum = 0;
        long cur = 0;

        for (int i = 0; i < n; i++) {
            sum += nums[i];
            cur += (long) i * nums[i];
        }

        long best = cur;

        // 递推计算所有旋转的函数值
        for (int k = 1; k < n; k++) {
            cur = cur + sum - (long) n * nums[n - k];
            if (cur > best) {
                best = cur;
            }
        }

        return (int) best;
    }
}

func maxRotateFunction(nums []int) int {
	n := len(nums)
	var sum int64
	var cur int64

	for i, val := range nums {
		sum += int64(val)
		cur += int64(i) * int64(val)
	}

	best := cur

	// 递推计算所有旋转的函数值
	for k := 1; k < n; k++ {
		cur = cur + sum - int64(n)*int64(nums[n-k])
		if cur > best {
			best = cur
		}
	}

	return int(best)
}

相似题目

题目	难度	考察点
189. 轮转数组	中等	数组旋转
724. 寻找数组的中心下标	简单	前缀和
238. 除自身以外数组的乘积	中等	前缀/后缀
643. 子数组最大平均数 I	简单	滑动窗口
918. 环形子数组的最大和	中等	环形数组

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/82792358