优化到O(n))
刷题这么久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) 16F(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 16F(2) F(1) sum - 4*nums[2] 16 15 - 8 23F(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] 为例元素F(0) 系数F(1) 系数F(2) 系数F(3) 系数40123312302230163012从这张表能清楚看到每个元素的系数实际上是在循环递减/递增。正因为存在这种整齐的循环规律才能推导出 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 20000nums[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(vectorint 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) 都列出来观察它们的差值与被旋转元素的关系。多试几组不同的数组规律很快就能浮出水面。很多看似复杂的公式其实都是从具体例子中归纳出来的。这道题本身不难但它是训练这种“先观察、后推导”思维的好素材值得你花半小时把它彻底吃透。
刷题这么久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) 16F(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 16F(2) F(1) sum - 4*nums[2] 16 15 - 8 23F(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] 为例元素F(0) 系数F(1) 系数F(2) 系数F(3) 系数40123312302230163012从这张表能清楚看到每个元素的系数实际上是在循环递减/递增。正因为存在这种整齐的循环规律才能推导出 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 20000nums[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(vectorint 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) 都列出来观察它们的差值与被旋转元素的关系。多试几组不同的数组规律很快就能浮出水面。很多看似复杂的公式其实都是从具体例子中归纳出来的。这道题本身不难但它是训练这种“先观察、后推导”思维的好素材值得你花半小时把它彻底吃透。
