企业官网建设流程全解析

刷题这么久，LeetCode 396“旋转函数”是我觉得特别适合用来理解“数学推导如何直接干掉暴力枚举”的一道经典题。题目本身不算难，但它的价值在于：表面上是一道模拟题，实际上考的是你能不能从一系列旋转操作里找出递推关系。我见过不少朋友一上来就写两层循环，结果数据一上来就超时，然后卡在那里不知道问题出在哪。这篇文章我会把整道题的完整推导链路、代码实现、边界坑点一次讲清楚，尤其是那个核心递推公式是怎么来的，以及为什么它能从 O(n²) 优化到 O(n)。

这道题适合三类人：一是准备面试、正在刷 LeetCode 热题 100 的朋友；二是刚学完数组和前缀和、想找一道中等难度的题练手的学习者；三是已经会做、但想搞清楚“为什么这么推”的进阶玩家。无论你处于哪个阶段，只要跟着我把样例手推一遍，把公式变形看懂，这题就彻底拿下了。

1. 题目到底在问什么：旋转函数与累加和

1.1 原题描述与术语拆解

LeetCode 396 的原题描述是这样的：给定一个长度为 n 的整数数组 nums，定义一个旋转函数 F(k)，表示数组旋转 k 次之后，每个元素乘以它的下标，然后全部加起来的结果。这里的“旋转一次”是指把数组整体往右移动一位，最后一位元素跑到最前面。

举个具体例子，nums = [4, 3, 2, 6]，长度 n = 4。

• F(0) = 0*4 + 1*3 + 2*2 + 3*6 = 0 + 3 + 4 + 18 = 25
• 旋转一次得到 [6, 4, 3, 2]，F(1) = 0*6 + 1*4 + 2*3 + 3*2 = 0 + 4 + 6 + 6 = 16
• 旋转两次得到 [2, 6, 4, 3]，F(2) = 0*2 + 1*6 + 2*4 + 3*3 = 0 + 6 + 8 + 9 = 23
• 旋转三次得到 [3, 2, 6, 4]，F(3) = 0*3 + 1*2 + 2*6 + 3*4 = 0 + 2 + 12 + 12 = 26

题目要求返回所有 F(k) 里的最大值，这里的最大值是 26。注意题目说的是“旋转”，不是“翻转”，所以方向固定，每次循环右移一位。

1.2 数据范围与隐藏考点

原题的数据范围是：n 最大到 2*10^4，数组元素取值范围是 [-10^4, 10^4]。这个范围决定了暴力解法必挂。设想一下，如果 n = 20000，暴力解法要计算 20000 个旋转状态，每个状态里又要累加 20000 个乘积，总计算量是 4*10^8 次乘法加法，在 LeetCode 的评测环境里基本是超时边缘甚至直接 TLE。更关键的是，这道题的时间限制通常只有 1 秒左右，所以 O(n²) 是绝对过不去的。

我还想多说一句：这道题的数值上限也值得注意。F(k) 最大大概是 n * max(nums) * n 的量级，也就是 2*10^4 * 10^4 * 2*10^4 = 4*10^12，超出了 32 位 int 的范围。所以代码里必须用 long/long long 来存结果和累加值，这也是一个很常见的坑点，后面我会再强调。

1.3 为什么它被归为“数学推导”类题目

很多人第一次看到这题，直观反应就是按部就班地模拟：每次旋转数组，然后重新计算。这个思路本身没有错，但它没有利用到“相邻两次旋转结果之间的关系”。题目真正想检验的，是你能否把重复计算的部分抽象出来，找到一个从 F(k-1) 推导到 F(k) 的常数时间变换。这种“相邻状态递推”的思想，在动态规划、滑动窗口、前缀和问题里反复出现，所以 LeetCode 官方把它标记为中等难度，实际上它的思维难度比代码难度高。

2. 暴力解法与它的致命瓶颈

2.1 最直接的模拟思路

如果你第一次见到这题，最稳妥的做法就是照着题意写。用 Python 写的话，很多人会这样：

def maxRotateFunction(nums): n = len(nums) if n == 0: return 0 res = float('-inf') for k in range(n): rotated = nums[-k:] + nums[:-k] if k else nums[:] s = 0 for i, val in enumerate(rotated): s += i * val res = max(res, s) return res

这段代码在思路上完全正确，按照定义计算每个旋转状态。但问题在于，它做了 n 次旋转，每次旋转的切片操作本身是 O(n)，再加上内层累加 O(n)，整体就是 O(n²)。我拿本地环境测试过，n = 20000 的时候，这个函数跑了大概 4 到 5 秒，在 LeetCode 上基本就是 TLE 的结果。

2.2 为什么 O(n²) 在这里不可接受

你可能会想，4*10^8 次操作是不是也还行？这取决于编程语言和执行环境。Python 在纯循环下每秒大概能跑 10^7 到 10^8 次简单操作，但这里涉及切片、列表拼接、乘法、加法，实际效率要低得多。即使在 C++ 里，4*10^8 次操作也可能逼近时间限制。LeetCode 的评测机通常不会给你 5 秒钟。所以，我们必须找一种方法，把两层循环压成一层循环。

另外我还要指出一点：这种“每个状态都从零开始算”的方式，完全浪费了相邻状态之间的共性。从 F(0) 变到 F(1)，数组只发生了“整体右移一位”的变化，我们其实可以知道哪些贡献变了、哪些贡献没变。这正是动态规划递推的切入点。

2.3 暴力法的改进空间在哪

我们观察一下相邻旋转的关系。手动对比 F(0) = 25 和 F(1) = 16，差值是多少？25 - 16 = 9。对于 [4, 3, 2, 6] 来说，总和 sum = 15，而 n = 4。你会发现一个有趣的现象：25 - 16 = 9，而 sum - 4 * 6 = 15 - 24 = -9，正好差一个负号，所以 F(1) = F(0) + sum - n * nums[n-1]？让我仔细验算：F(1) = 16，F(0) + sum - 4 * nums[3] = 25 + 15 - 24 = 16。成立。这个公式不是巧合，它就是我们要推导的核心递推关系。有了它，我们不需要每次重新累加，只需要知道上一次的 F 值、数组总和 sum，以及“这次被移到最前面的那个元素”，就能在 O(1) 时间内算出新的 F 值。

3. 核心递推公式的完整推导

3.1 从一次旋转的视角看下标变化

设数组长度为 n，原始数组记为 A[0], A[1], ..., A[n-1]。F(0) = 0*A[0] + 1*A[1] + ... + (n-1)*A[n-1]。

现在旋转一次，新数组变成 A[n-1], A[0], A[1], ..., A[n-2]。于是：

F(1) = 0*A[n-1] + 1*A[0] + 2*A[1] + ... + (n-1)*A[n-2]。

我们想要知道 F(1) 和 F(0) 之间差了多少。做法很简单：把 F(1) 的每一项跟 F(0) 的每一项对比。A[0] 在 F(0) 里的系数是 0，在 F(1) 里的系数是 1，增加了 1*A[0]；A[1] 的系数从 1 变成 2，增加了 1*A[1]；以此类推，A[n-2] 的系数从 n-2 变成 n-1，增加了 1*A[n-2]；唯独 A[n-1] 的系数从 n-1 变成了 0，减少了 (n-1)*A[n-1]。

把所有增量加起来就是 A[0] + A[1] + ... + A[n-2] - (n-1)*A[n-1]。注意前 n-1 项的和等于 sum - A[n-1]，所以增量 = (sum - A[n-1]) - (n-1)*A[n-1] = sum - n*A[n-1]。

结论：F(1) = F(0) + sum - n*A[n-1]。

3.2 推广到一般情况：F(k) 与 F(k-1)

上面的推导虽然只针对从 F(0) 到 F(1)，但它揭示了一个通用规律。只要数组做一次旋转，除了“被旋到最前面的那个元素”（也就是上一次旋转前的最后一个元素）之外，其他所有元素的系数都加 1。因为系数加 1，所以它们的贡献总和增加了它们的数值总和；而被旋到最前面的那个元素，它的系数直接从 n-1 掉到 0，贡献减少了 (n-1) 倍它的值。

设数组总和为 sum，上一次旋转前的最后一个元素是 nums[n-k]，其中 k 表示当前计算的是第 k 次旋转。更精确地说，如果当前要算 F(k)，那么从 F(k-1) 到 F(k)，被移到最前面的元素是原始数组中的 nums[n-k]。于是递推公式可以写成：

F(k) = F(k-1) + sum - n * nums[n-k]

这里 n-k 是原始数组的下标。举例验证：在前面的例子中，F(1) = F(0) + sum - 4*nums[3] = 25 + 15 - 24 = 16；F(2) = F(1) + sum - 4*nums[2] = 16 + 15 - 8 = 23；F(3) = F(2) + sum - 4*nums[1] = 23 + 15 - 12 = 26。完全吻合。

3.3 用矩阵视角重新理解（加深记忆）

如果你对线性代数比较敏感，可以把整个旋转过程看成数组下标的一种循环置换。F(k) 本质上是一个加权内积：F(k) = Σ i * B[i]，其中 B 是旋转后的数组。从 F(k-1) 到 F(k)，相当于把权重向量 [0, 1, 2, ..., n-1] 循环右移一位，再和原始数组做内积。这样每次旋转变化的只是权重分配，而数组本身不变。这就解释了为什么总和 sum 会出现在公式里：权重整体加 1 带来的贡献增量就是所有元素之和，唯一例外是被挤出高权重位置的那个元素，它需要额外补偿。

为了更直观，我画过一个表格来记录每个元素在 F(k) 中的系数。以 [4, 3, 2, 6] 为例：

从这张表能清楚看到，每个元素的系数实际上是在循环递减/递增。正因为存在这种整齐的循环规律，才能推导出 O(1) 的相邻递推。

4. 从公式到代码：多语言实现与细节打磨

4.1 算法流程与时间复杂度分析

完整算法分三步：

• 第一步，遍历一次数组，算出总和 sum，同时算出 F(0)（也就是 Σ i*nums[i]），时间 O(n)。
• 第二步，从 k = 1 到 k = n-1，用递推公式 F(k) = F(k-1) + sum - n*nums[n-k] 逐个计算，每次 O(1)。
• 第三步，在计算过程中维护最大值。

总时间复杂度 O(n)，空间复杂度 O(1)。这里注意，我们不需要真的旋转数组，也不需要额外存储 F 序列，只需要一个变量记录前一个 F 值和当前最大值。

4.2 Python 实现及逐行解释

def maxRotateFunction(nums): n = len(nums) if n == 0: return 0 total = sum(nums) f = sum(i * nums[i] for i in range(n)) res = f for k in range(1, n): f = f + total - n * nums[n - k] if f > res: res = f return res

这段代码中，最容易写错的就是 nums[n - k] 这个下标。当 k = 1 时，它代表原始数组的最后一个元素，这正是第一次旋转被移到最前面的元素；当 k = 2 时，它代表原始数组的倒数第二个元素，也就是第二次旋转被移到最前面的元素。这个下标的循环方向是从后往前，一定不要写成 nums[k-1]。我在本地调试的时候，就曾因为把这个下标写反，导致结果差之千里。

另一个容易忽略的地方是 f 的类型。在 Python 里整数不会溢出，所以这里不需要额外处理，但如果你用 C++ 或 Java，就一定要用 long long 或者 long，否则当数组元素很大的时候，整数溢出会让你得到一个完全错误的最大值。

最后，n = 1 的情况也要注意。如果只有一个元素，那么不管旋转多少次，数组都不变，F(0) = 0*nums[0] = 0，答案永远是 0。上面的代码在 n = 1 时，range(1, 1) 为空，直接返回 f = 0，所以是正确的。但如果你在循环里用了 nums[n-k]，当 n = 1 且 k = 1 时下标是 nums[0]，实际上不会进入循环，所以没问题。不过为了代码健壮性，我仍然建议显式处理一下 n <= 1 的情况，避免以后自己看代码时疑惑。

4.3 Java 实现及边界处理

class Solution { public int maxRotateFunction(int[] nums) { int n = nums.length; if (n == 0) return 0; long sum = 0; long f = 0; for (int i = 0; i < n; i++) { sum += nums[i]; f += (long) i * nums[i]; } long res = f; for (int k = 1; k < n; k++) { f = f + sum - (long) n * nums[n - k]; if (f > res) res = f; } return (int) res; } }

这里我刻意把 sum、f、res 都声明为 long。你看，如果不用 long，当 n = 20000，nums[i] = 10000 时，f 的值最大会接近 2*10^4 * 10^4 * 2*10^4 = 4*10^12，而 int 最大只能到 2.1*10^9，差了三个数量级。即使题目最后要求返回 int，计算过程中也绝不能省略 long。还有一个小细节：对于负数元素，long 类型也不会出问题，递推公式中 sum - n*nums[n-k] 可能为负，f 会变小，但这正是我们需要的，因为我们要的是最大值，允许它波动。

4.4 C++ 实现与性能对比

class Solution { public: long long maxRotateFunction(vector<int>& nums) { int n = nums.size(); if (n == 0) return 0; long long sum = 0; long long f = 0; for (int i = 0; i < n; ++i) { sum += nums[i]; f += 1LL * i * nums[i]; } long long res = f; for (int k = 1; k < n; ++k) { f = f + sum - 1LL * n * nums[n - k]; res = max(res, f); } return res; } };

注意 C++ 里 1LL * i * nums[i] 的写法，是为了把 i*nums[i] 先转成 long long 再计算，否则 i 是 int、nums[i] 是 int，两者相乘可能直接在 int 域内溢出。这种细节在面试中很容易被追问，答得上来说明你确实理解溢出问题。

我在本机用随机数组对三种语言的实现做了简单测试，对于 n = 20000 的数组，C++ 运行时间大约在 1 毫秒以内，Java 大约 2 到 3 毫秒，Python 大约 20 到 30 毫秒。虽然 Python 最慢，但在这个量级下，O(n) 的算法完全够用。

5. 常见错误与排查技巧实录

5.1 最常见的三类错误

第一类错误是在递推公式中使用了错误的“被旋转元素”。很多人的第一版代码会这样写：

f = f + total - n * nums[k]

直觉上以为第 k 次旋转就是把 nums[k] 移到最前面，但实际上，第 k 次旋转移到最后面的元素是原始数组的 nums[n-k]。这个错误很隐蔽，因为当数组恰好是 [1, 2, 3, 4] 这样的连续正数时，错误写法在某些 k 上的结果可能碰巧正确，让你误以为代码没问题。建议在测试时用 [4, 3, 2, 6] 这种非对称数组，逐项核对 F(k) 的期望值。

第二类错误是忘记处理 n = 0 的情况。虽然 LeetCode 的输入约束通常不会出现空数组，但在本地自测时，空数组会返回 0 还是抛异常，直接影响代码的健壮性。我习惯在函数开头加一个 if n == 0 的防护。

第三类错误是使用 int 存储中间结果，导致大数溢出后最大值计算错误。这类错误特别阴险，因为你可能得到的 res 是一个看似合理的正数，但实际上已经是溢出后的截断值。只要数组长度和元素值较大，int 就会爆掉。

5.2 如何设计高质量的测试用例

题目本身简单，但测试用例可以设计得更全面。我个人会准备几组典型数据：

• [1, 2, 3, 4, 5]：连续递增数组，用来验证递推公式的累计效果。
• [100, -100, 50, -50]：正负交替，验证负数对最大值的影响。
• [0, 0, 0, 0]：全零数组，验证 sum = 0 时公式依然成立，结果恒为 0。
• [2147483647, 2147483647]：接近 int 上限的大数，专门测试溢出问题。
• [5]：单元素数组，验证旋转循环不进入时结果是否正确。

用这些用例逐组手算，再和代码输出对比，基本能覆盖所有边界条件。尤其是大数用例，如果代码里用的是 int，大概率会在这组测试上暴露问题。

5.3 一个容易忽略的细节：为什么可以用原始数组下标

你在理解递推公式时，可能会困惑一个问题：数组每旋转一次，元素位置就变了，为什么公式里还能用 nums[n-k] 这种“原始下标”？关键在于，旋转操作并没有改变元素本身，只是改变了它们的位置。当我们说“第 k 次旋转把哪个元素移到了最前面”，完全可以通过原始数组的下标来描述。第 1 次旋转时最前面的元素是原始数组最后一个元素；第 2 次旋转时最前面的元素是原始数组倒数第二个元素；以此类推。所以 nums[n-k] 这个写法是准确的，它描述的是第 k 次操作时被挪到 0 号位置的那个原始元素。

5.4 面试中的延伸追问

这道题经常会被面试官加以变体追问。比如：如果旋转方向改成每次向左移动一位，递推公式会变成什么？答案是 F(k) = F(k-1) + sum - n*nums[k-1]，因为向左移动一位时，被移到最前面的元素是原始数组的 nums[k-1]。再比如：如果要求输出所有 F(k) 而不仅仅是最大值，那就把每个 f 存进结果数组，算法不变。如果数组元素非常大，还可以考虑用 Python 的任意精度整数，但 LeetCode 通常不需要。

6. 拓展思维：从旋转函数到滑动窗口思想

6.1 递推公式背后的“增量思想”

这道题最值得借鉴的地方，是它展示了如何处理“整个数组发生同一种变化”的问题。很多算法题的难点不在于最终的代码，而在于你是否能发现相邻状态之间的结构。旋转函数用到的技巧，本质上和滑动窗口非常像：窗口从左往右移动时，没有必要重新计算窗口内所有元素的和，只要减去离开窗口的元素、加上进入窗口的元素即可。旋转函数也是一样，每次旋转只“移走”一个元素的高权重位置，同时让其它元素权重普遍加一，所以我们只需要修正这两部分的差值。

如果你能掌握这种“增量维护”的思想，那么以后遇到这类题目都会更有方向。比如 LeetCode 的“最小覆盖子串”“无重复字符的最长子串”甚至“最大子数组和”的某些变体，其实都隐藏着类似的增量逻辑。

6.2 与相似题目的对比学习

LeetCode 396 和 LeetCode 189“旋转数组”是明显相关的一对题目。后者要求原地旋转数组，考的是数组翻转技巧；前者要求计算旋转后的加权和，考的是数学递推。建议把这两题放在一起刷，加深你对“旋转”类操作的理解。另外，LeetCode 的“轮转数组”系列还有“寻找旋转排序数组中的最小值”，那道题考的是二分查找，和旋转函数又是一类变体。把这些题串起来学习，你会形成一张以“旋转”为核心的知识网络。

6.3 我个人的刷题心得

说实话，我第一次做这道题的时候，也是老老实实写了暴力解，结果超时后愣住了。后来耐下心把 F(1) 和 F(0) 的每一项拆开对比，才真正理解那个递推公式。从那以后，我养成了一个习惯：遇到任何涉及“连续变化状态”的题目，先问自己一句，相邻两个状态之间到底发生了什么变化？这个问题的答案，往往就是优化算法的钥匙。

如果你正在准备面试，我建议你不仅能默写代码，还能在白板上把递推公式推导一遍。面试官大概率会追问“为什么是这样”，你要是能当场推演，会留下非常深刻的印象。

最后再分享一个小技巧：如果一时写不出递推公式，可以先手算 n = 3 或 n = 4 的例子，把 F(0)、F(1)、F(2)、F(3) 都列出来，观察它们的差值与被旋转元素的关系。多试几组不同的数组，规律很快就能浮出水面。很多看似复杂的公式，其实都是从具体例子中归纳出来的。这道题本身不难，但它是训练这种“先观察、后推导”思维的好素材，值得你花半小时把它彻底吃透。