LeetCode 396. 旋转函数

2022-04-28 HGNULB 约 8 分钟

文章信息 7 个分类 3 个标签

分类

题目描述

✅ 396. 旋转函数

题意分析

给定长度为 $n$ 的数组，把它顺时针旋转 $k$ 次得到新数组，然后计算「每个元素乘以它在新数组中的下标」的总和，记作 $F(k)$。$k$ 可以取 $0$ 到 $n-1$，要求返回这 $n$ 个值里的最大者。

换个说法更好理解：旋转并不改变元素的相对环形次序，改变的只是「谁拿到系数 $0$」。$F(k)$ 就是把系数序列 $0, 1, 2, \ldots, n-1$ 沿着环整体挪了 $k$ 格之后的加权和。

约束里 $n$ 可以到 $10^5$，而候选值有 $n$ 个，每个若都重新求一遍加权和就是 $O(n^2)$，在这个规模下会超时。这个数量级差距就是本题要求找递推关系的信号。

边界方面：$n = 1$ 时只有 $F(0) = 0$ 一个候选；数组元素可以为负，所以答案可能是负数，初值不能简单地设成 $0$；虽然题目保证最终答案落在 $32$ 位整数范围内，但求和过程中系数最大到 $n-1$，用 $64$ 位承载中间量更稳妥。

解法：递推公式

核心思路

朴素做法是对每个 $k$ 都重新遍历一遍数组算加权和，$n$ 个候选共 $O(n^2)$ 次乘加。瓶颈很明显：相邻两个候选之间，数组本身没变，只是每个元素的系数整体挪了一格，却被完整重算了一遍。

于是去观察 $F(k)$ 与 $F(k-1)$ 的差。从 $F(k-1)$ 到 $F(k)$，旋转再进一格，除了一个元素外，其余每个元素的系数都恰好增加 $1$，这部分贡献的增量正好是这些元素之和。唯一的例外是原本系数为 $n-1$ 的那个元素，它绕回队首，系数从 $n-1$ 掉到 $0$，减少了 $n-1$。把「所有元素系数各加 $1$」写成加上总和 $\text{sum}$，那个例外元素就相当于多加了 $1$ 又要减掉 $n$，合并后正好是减去 $n$ 倍的它自身。

剩下要确定的是这个「绕回队首」的元素是谁。在第 $k$ 次旋转时，被推到系数 $0$ 位置的是原数组中下标为 $n-k$ 的元素。由此得到递推式 $F(k) = F(k-1) + \text{sum} - n \cdot \text{nums}[n-k]$，其中 $1 \le k \le n-1$。

状态定义就是 $F(k)$ 表示旋转 $k$ 次后的加权和，初值 $F(0) = \sum_{i=0}^{n-1} i \cdot \text{nums}[i]$。由于转移只依赖前一项，可以用一个滚动变量承载，边推边取最大值，一趟扫完即可。

解题步骤

第一遍遍历同时求两样东西：数组总和 $\text{sum}$，以及初始加权和 $F(0) = \sum i \cdot \text{nums}[i]$。两者共用一次循环，避免多扫一遍。

把 best 初始化为 $F(0)$ 而不是 $0$ 或某个常量。数组元素允许为负，$F$ 的取值可以全为负数，用 $0$ 起头会把答案抬高成错误的 $0$。

从 $k = 1$ 循环到 $k = n-1$，每轮按递推式更新滚动变量：加上 $\text{sum}$，再减去 $n \cdot \text{nums}[n-k]$。加 $\text{sum}$ 对应「所有元素系数整体加一」，减 $n \cdot \text{nums}[n-k]$ 对应「队尾元素绕回队首，系数从 $n-1$ 直接归零」这一次性修正。

下标写成 $n-k$ 而非 $n-k-1$ 或 $k$，因为第 $k$ 次旋转把原下标 $n-k$ 的元素送到了系数 $0$ 的位置。$k$ 从 $1$ 取到 $n-1$，对应的下标从 $n-1$ 递减到 $1$，恰好覆盖除 $\text{nums}[0]$ 外的所有元素——$\text{nums}[0]$ 在 $F(0)$ 时就已经在系数 $0$ 上，不会再被重复扣减。

每轮更新后与 best 比较并取较大者。更新与比较必须在同一轮内完成，先比较后更新会漏掉最后一个候选。

循环结束后把 best 转回 $32$ 位整型返回。

以 [4,3,2,6] 走一遍：$n = 4$。第一遍遍历得 $\text{sum} = 4+3+2+6 = 15$，$F(0) = 0 \times 4 + 1 \times 3 + 2 \times 2 + 3 \times 6 = 0 + 3 + 4 + 18 = 25$，best 初始化为 $25$。$k = 1$ 时，绕回队首的是 $\text{nums}[4-1] = \text{nums}[3] = 6$，于是 $F(1) = 25 + 15 - 4 \times 6 = 25 + 15 - 24 = 16$；直接验算旋转一次得到的数组是 $[6,4,3,2]$，加权和为 $0 \times 6 + 1 \times 4 + 2 \times 3 + 3 \times 2 = 16$，吻合。best 仍为 $25$。$k = 2$ 时，绕回的是 $\text{nums}[2] = 2$，$F(2) = 16 + 15 - 4 \times 2 = 23$；验算数组 $[2,6,4,3]$ 的加权和为 $0 + 6 + 8 + 9 = 23$，吻合。best 仍为 $25$。$k = 3$ 时，绕回的是 $\text{nums}[1] = 3$，$F(3) = 23 + 15 - 4 \times 3 = 26$；验算数组 $[3,2,6,4]$ 的加权和为 $0 + 2 + 12 + 12 = 26$，吻合。此时 $26 > 25$，best 更新为 $26$。循环结束返回 $26$。

代码实现

// 旋转一次的递推关系：F(k) = F(k-1) + sum - n \* nums[n-k]。
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;
    }
}

// 旋转一次的递推关系：F(k) = F(k-1) + sum - n \* nums[n-k]。
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)
}

复杂度分析

时间复杂度：$O(n)$，$n$ 为数组长度。第一趟循环 $n$ 次求出总和与 $F(0)$，第二趟循环 $n-1$ 次按递推式滚动，每轮只有一次乘法、两次加减和一次比较，合计两遍线性扫描。

空间复杂度：$O(1)$。只用了总和、滚动的当前函数值、历史最大值三个标量，没有为 $n$ 个候选开数组，也没有构造任何旋转后的副本。

关键点总结

一批候选答案需要逐个求值时，先问「相邻两个候选之间差了什么」。若差值能用 $O(1)$ 表达，整体复杂度就能从平方降到线性，这是递推优化最通用的入口。

推导差值时把「共性变化」和「个别修正」分开写。本题共性是所有系数加一（贡献 $\text{sum}$），个别是队尾元素系数从 $n-1$ 归零（修正 $-n \cdot \text{nums}[n-k]$），拆开后公式自然浮现，硬凑很难对。

旋转类问题不要真的去构造旋转后的数组。系数的环形移动完全可以用下标算术表达，构造副本既费空间又容易在下标映射上出错。

涉及负数的极值问题，初值必须取自真实候选（这里是 $F(0)$）而不是 $0$ 或凭空的常量，否则会引入不存在的答案。

面试视角：面试官期待的是你先说出 $O(n^2)$ 的朴素解，再当场推出相邻项之差。推导过程比结论更重要，建议在纸上写出 $F(1)-F(0)$ 的展开式给对方看。

面试视角：常见追问是「$n-k$ 这个下标怎么来的」和「$k$ 的取值范围为什么到 $n-1$」。回答时结合「$\text{nums}[0]$ 在 $F(0)$ 时已占据系数 $0$」这一点，能显示你验证过下标覆盖的完备性。

易错点总结

错误写法：递推中扣减的下标写成 $\text{nums}[k]$ → 对 [4,3,2,6]，$k=1$ 会算成 $25+15-4\times3=28$，而正确的 $F(1)$ 是 $16$，最终返回 $28$ 这个根本不存在的值。

错误写法：下标写成 $\text{nums}[n-k-1]$ → 对 [4,3,2,6]，$k=1$ 扣的是 $\text{nums}[2]=2$，算得 $32$，同样偏离真实的 $16$。

错误写法：把 best 初始化为 $0$ → 对全负数组如 [-1,-2,-3]，真实的三个候选都是负数，会错误返回 $0$。

错误写法：best 初始化为 Integer.MIN_VALUE 但用 int 承载滚动值 → 长数组下 $F(0)$ 的中间累加可能超出 $32$ 位，一次溢出后所有后续递推值全错。

错误写法：递推式写成 $F(k) = F(k-1) + \text{sum} - (n-1) \cdot \text{nums}[n-k]$ → 少减了一份该元素本身，对 [4,3,2,6] 的 $k=1$ 会得到 $22$ 而非 $16$；系数从 $n-1$ 归零是减 $n-1$ 份，但这一份已被「整体加一」多加过一次，合计必须减 $n$ 份。

错误写法：循环范围写成 $k$ 从 $1$ 到 $n$ → 多算一轮会扣减 $\text{nums}[0]$，等价于又转回原始排列，虽然值恰好回到 $F(0)$ 不影响最大值，但下标 $n-k$ 在 $k=n$ 时为 $0$ 之外若写成 $n-k-1$ 则直接越界成 $-1$。

错误写法：先比较后更新，即在循环体开头就用旧值和 best 比较 → 最后一次旋转产生的 $F(n-1)$ 从未参与比较，对 [4,3,2,6] 会漏掉最大的 $26$，返回 $25$。

错误写法：为每个 $k$ 真的构造一份旋转后的数组再求和 → 时间退化成 $O(n^2)$，$n = 10^5$ 时直接超时。

错误写法：把 $\text{sum}$ 误理解成 $F(0)$ 或在循环中反复重算总和 → 前者让递推式彻底失效，后者把每轮的 $O(1)$ 变成 $O(n)$，退回平方复杂度。

错误写法：$n = 1$ 时不做保护而直接进入第二个循环 → 循环条件 $k < 1$ 本身不成立所以安全，但若循环写成 do-while 或范围取到 $k \le n-1$ 之外，就会访问 $\text{nums}[1]$ 越界。

相似题目

题目	难度	考察点
918. 环形子数组的最大和	中等	同为环形结构上的极值，用「总和减最小子数组和」处理跨界情况
189. 轮转数组	中等	真正执行旋转，考察三次反转的原地技巧而非系数递推
238. 除了自身以外数组的乘积	中等	同样靠相邻结果的关系避免重复计算，方向是前后缀乘积
303. 区域和检索 - 数组不可变	简单	前缀和预处理让区间查询降为 $O(1)$，是递推思想的最基础形态
724. 寻找数组的中心下标	简单	用总和与前缀和的关系一趟扫出答案，无需为每个位置重新求和