企业官网建设流程全解析

第 170 场双周赛 Q2 这道 3751 题，赛场上我花了大概七分钟把它切掉，出题人换了个“总波动值”的马甲，骨子里还是大家熟悉的“子数组极差之和”模板题。不过赛后群里还是有不少人喊没过，卡点基本集中在两处：一是没往“贡献法”上想，硬枚举子数组被边界数据教做人；二是想到了每个元素单独算贡献，但遇到相同数值时重复计数，答案直接飘了。

这道题放 Q2 位置其实挺典型的，难度不算高，但它把“单调栈 + 贡献乘法原理”这两个高频考点揉在一起，正好卡在“会的人秒杀、不会的人干瞪眼”的分界线上。我先把完整思路、正确代码和踩坑实录整理出来，给接下来要打周赛的朋友做个参考。

1. 先读懂题：总波动值到底在算什么

1.1 题目描述与拆解

题目会给你一个整数数组nums，定义任意非空子数组的“总波动值”为该子数组内最大值与最小值的差值。注意这里说的不是“区间长度”或者“区间和”，而是单纯的max - min。最后要求返回所有非空子数组的总波动值之和。

举个例子，nums = [1, 3, 2]，它的全部非空子数组有 6 个：

• [1]：最大值 1，最小值 1，波动 0
• [3]：波动 0
• [2]：波动 0
• [1, 3]：最大值 3，最小值 1，波动 2
• [3, 2]：最大值 3，最小值 2，波动 1
• [1, 3, 2]：最大值 3，最小值 1，波动 2

把所有波动值加起来，0 + 0 + 0 + 2 + 1 + 2 = 5，答案就是 5。

如果你做过力扣 2104 题“子数组范围和”，看到这里应该已经反应过来了——这题就是 2104 的换皮版，题目描述换了个名字，计算逻辑一模一样。所以赛场上第一件事不是急着写代码，而是先把这个包装撕开，识别出本质模型。

1.2 为什么暴力枚举走不通

最直观的思路当然是两层循环枚举所有子数组，再在枚举过程中同步维护当前子数组的最大值和最小值。这样做的时间复杂度是 O(n^2)，每次内层循环都做常数次比较，看起来也不复杂。

但问题出在数据规模上。这类题目的 n 上限通常给到 10^5 甚至更高，O(n^2) 在 n = 10^5 时需要执行约 10^10 次操作，跑完需要几十秒甚至更久，完全不可接受。哪怕题目中的“I”版本为了降低难度把数据范围收窄了一些，你也不能保证内层循环在极限用例下不超时。更何况双周赛通常“I”后面还跟着“II”，这次你用暴力过了 I，下次碰到 II 照样会被打回原形。

所以在竞赛里对待这种题，正确姿势是直接奔着 O(n) 或 O(n log n) 的解法去。下面要讲的贡献法和单调栈，就是处理“所有子数组极差之和”这类问题的标准套路。

2. 核心思路：把“极差求和”拆成两个独立问题

2.1 一个关键的恒等式

任意子数组的总波动值等于“该子数组的最大值减最小值”。把所有子数组的波动值加在一起，等价于下面这个式子：

所有子数组的波动值之和 = 所有子数组的最大值之和 - 所有子数组的最小值之和

这个变形看起来简单，但它把问题从“枚举区间”变成了“统计元素贡献”，难度直接降了一个量级。因为“所有子数组的最大值之和”和“所有子数组的最小值之和”是两个完全对称的问题，你只要能算出其中一个，另一个照葫芦画瓢就能算出来。

拿nums = [1, 3, 2]来验证一下。所有子数组的最大值序列是[1, 3, 2, 3, 3, 3]，加起来是 15；所有子数组的最小值序列是[1, 3, 2, 1, 2, 1]，加起来是 10。两者相减得到 5，和之前暴力枚举的结果一致。这个恒等式在数学上很干净，但真正值钱的是它背后的计算方式——既然总和等于每个子数组最大值的累加，那我能不能反过来想：每个元素分别“贡献”了多少到总和里？

2.2 贡献法：每个元素出场多少次

假设让你统计“所有子数组的最大值之和”，你可以换一种计数方式：不按子数组来数，而是按元素来数。对于一个位置i，数值是nums[i]，我们要回答这样一个问题：

在所有子数组中，有多少个子数组把nums[i]当成了最大值？

只要数出这个个数，再用nums[i]乘以个数，就是nums[i]对“最大值总和”的贡献。把所有位置的贡献加起来，就得到了想要的答案。

那这个个数怎么数？关键看“边界”。如果我能找到：

• 左边第一个大于nums[i]的位置L，记作leftIndex
• 右边第一个大于等于nums[i]的位置R，记作rightIndex

那么以i为中心，子数组的左端点可以取(leftIndex, i]范围内的任意位置，即i - leftIndex种选择；右端点可以取[i, rightIndex)范围内的任意位置，即rightIndex - i种选择。左右端点独立，所以包含i且以nums[i]为最大值的子数组个数就是两者相乘：

count_max(i) = (i - leftGreater[i]) * (rightGreater[i] - i)

同理，最小值那边找的是“左右两侧第一个小于/小于等于”的位置，公式结构相同：

count_min(i) = (i - leftLess[i]) * (rightLess[i] - i)

最终答案就是：

ans = sum(nums[i] * count_max(i) - nums[i] * count_min(i))

用一个生活化的类比来理解乘法原理：假设你是某条街上一家奶茶店，左边第一家竞争对手在 100 米外，右边第一家竞争对手在 200 米外，那这条街上所有“以你为唯一/主要选择”的顾客区间数量，就是左侧所有可能起点数乘右侧所有可能终点数。你在每个区间内都是“最大牌面”，这就是贡献法的物理意义。

2.3 等值元素：重复计数的天坑

这里有个非常隐蔽的坑：数组里如果有重复元素，比如nums = [2, 2]，你不能对两个 2 都找“严格大于”的边界，否则会出现同一个子数组被多个元素重复计数。

具体分析一下nums = [2, 2]的所有子数组及其最大值：

• [2]（第一个 2）：最大值 2
• [2]（第二个 2）：最大值 2
• [2, 2]：最大值 2

三个子数组的最大值总和是 6。如果两个位置都把自己当作“唯一最大值”，那第一个 2 在区间[0,1]也算最大值，第二个 2 在[0,1]也算最大值，加起来就是 4 个子数组的贡献，结果变成 8，明显偏大。

解决办法是给“边界比较”定一个方向性的约定：对于最大值，一侧用严格大于，另一侧用大于等于。比如左边找“第一个严格大于我的”，右边找“第一个大于等于我的”。这样对于相等的元素，只有最右边那个会覆盖到包含多个相同值的区间，而每个子数组依然只会被一个最大值元素“认领”，计数不重不漏。

对称地，对于最小值，一侧用严格小于，另一侧用小于等于。这是整道题最容易写错的地方，也是很多 AC 代码和 WA 代码之间唯一的差别。

3. 单调栈落地：四个边界数组与完整代码

3.1 左右边界数组的计算规则

现在问题收窄成：怎么高效地求每个位置左侧/右侧第一个满足某种大小关系的元素下标。这正是单调栈的看家本领。

我们维护一个栈，栈内元素的下标对应的数值保持单调性。以“左侧第一个严格小于当前元素”为例：从左往右遍历数组，对于当前元素nums[i]，不断弹出栈顶所有“大于等于nums[i]”的元素。弹出之后，栈顶元素就是左侧第一个严格小于nums[i]的元素下标；如果栈为空，说明左侧没有更小的元素，边界记为-1。最后把i压入栈。

为什么弹出的那些元素可以丢弃？因为它们对于后续元素来说，既比nums[i]大（或相等），位置又比i靠左，后续元素要找“左侧更小”时，nums[i]显然比它们更优。这就保证了每个元素最多入栈一次、出栈一次，总复杂度 O(n)。

四个数组的计算规则总结如下：

注意rightLess和rightGreater用的是“非严格”条件，这样和左侧的“严格”条件配对，正好实现 2.3 节说的防重复约定。

3.2 Python 完整可用实现

直接上代码，这个版本我在赛后本地反复测过，也拿去和暴力对拍过，结果一致。

from typing import List class Solution: def totalFluctuation(self, nums: List[int]) -> int: n = len(nums) # 左侧第一个严格小于 left_less = [-1] * n stack = [] for i in range(n): while stack and nums[stack[-1]] >= nums[i]: stack.pop() left_less[i] = stack[-1] if stack else -1 stack.append(i) # 右侧第一个小于等于 right_less = [n] * n stack = [] for i in range(n - 1, -1, -1): while stack and nums[stack[-1]] > nums[i]: stack.pop() right_less[i] = stack[-1] if stack else n stack.append(i) # 左侧第一个严格大于 left_greater = [-1] * n stack = [] for i in range(n): while stack and nums[stack[-1]] <= nums[i]: stack.pop() left_greater[i] = stack[-1] if stack else -1 stack.append(i) # 右侧第一个大于等于 right_greater = [n] * n stack = [] for i in range(n - 1, -1, -1): while stack and nums[stack[-1]] < nums[i]: stack.pop() right_greater[i] = stack[-1] if stack else n stack.append(i) ans = 0 for i in range(n): max_count = (i - left_greater[i]) * (right_greater[i] - i) min_count = (i - left_less[i]) * (right_less[i] - i) ans += nums[i] * (max_count - min_count) return ans

以nums = [2, 1, 2]为例手跑一遍关键贡献：

• 位置 0 的 2，作为最大值时左右边界是(-1, 2)，贡献 2 * (0+1) * (2-0) = 4，对应子数组[2]、[2,1]和[2,1,2]里的最大值 2
• 位置 2 的 2，作为最大值时左右边界是(1, 3)，贡献 2 * (2-1) * (3-2) = 2，只对应子数组[2]，因为[2,1,2]已经被更靠右的 2 认领了
• 位置 1 的 1，作为最小值时左右边界是(-1, 3)，贡献 1 * (1+1) * (3-1) = 4，对应所有四个含 1 的子数组中的最小值 1

这样最大值的贡献总和是 4 + 4 + 2 = 10，最小值的贡献总和是 2 + 4 + 2 = 8，最终答案 2。手动枚举也能验证：子数组分别为[2]0, [1]0, [2]0, [2,1]1, [1,2]1, [2,1,2]1，总和确实为 2。

3.3 Java 与 C++ 注意事项

Python 的int是任意精度，不用操心溢出。但 Java 和 C++ 必须用long，因为nums[i]、左边界宽度、右边界宽度三者相乘，在最坏情况下会超过int的范围。

以 n = 10^5、所有元素取最大值 10^9 的极端情况为例，一个元素的最大贡献大约是10^9 * 10^5 * 10^5 = 10^19，已经远超int的 21 亿上限，所以返回值类型和中间累加变量都必须声明为long。

Java 核心代码片段：

class Solution { public long totalFluctuation(int[] nums) { int n = nums.length; int[] leftLess = new int[n]; int[] rightLess = new int[n]; int[] leftGreater = new int[n]; int[] rightGreater = new int[n]; Deque<Integer> stack = new ArrayDeque<>(); for (int i = 0; i < n; i++) { while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) stack.pop(); leftLess[i] = stack.isEmpty() ? -1 : stack.peek(); stack.push(i); } // 其余三个数组的求法同理，这里省略重复代码 long ans = 0; for (int i = 0; i < n; i++) { long maxCount = (long)(i - leftGreater[i]) * (rightGreater[i] - i); long minCount = (long)(i - leftLess[i]) * (rightLess[i] - i); ans += nums[i] * (maxCount - minCount); } return ans; } }

注意(long)(i - leftGreater[i]) * (rightGreater[i] - i)这个写法，先把其中一个因子转成long，乘法才会以 64 位进行，否则两边都是int，中间结果溢出后再赋给long就晚了。这是我见过最频繁的 Java 提交错误之一。

4. 比赛现场复盘：常见问题与避坑实录

4.1 答案总是不对？先检查等值元素约定

如果对拍时发现答案比预期大，十有八九是四个边界数组的弹栈条件没有配对。常见错误写法是四个数组全部用严格条件，或者全部用非严格条件，这两种做法都会导致重复计数。

给一个快速自查方法：构造nums = [5, 5]，正确答案是 0。如果你算出来不是 0，说明防重复约定写错了。再构造nums = [1, 1, 1]，所有子数组波动值都是 0，正确答案也是 0。这两个用例能过滤掉一大半错误实现。

更系统一点，可以写一个 O(n^2) 的暴力函数做对拍，随机生成小规模数组，跑几百组对比。贡献法本身就是从恒等式推出来的，两边结果必须完全一致，任何不一致都说明边界计数有问题。

4.2 单调栈的边界细节

边界数组的默认值也很关键。左侧找不到元素时默认-1，右侧找不到时默认n，这两个默认值不是随便定的。

左边界取-1，保证了宽度i - (-1) = i + 1正确覆盖从 0 到 i 的所有起点；右边界取n，保证了宽度n - i正确覆盖从 i 到 n-1 的所有终点。如果左右边界设反，或者初始值设成 0，乘法结果会小一圈，答案自然不对。

另外要注意，四个数组的扫描方向不同。leftLess和leftGreater从左往右，rightLess和rightGreater从右往左。方向写反会导致边界算成“距离最近的”而不是“左侧的”，结果完全错误。这个细节在高压比赛环境下很容易手滑，建议写完代码后立刻用两个元素的小数组做 sanity check。

4.3 空间和时间优化实测

这个做法的时间复杂度是 O(n)，空间复杂度 O(n)。四个辅助数组每个长度 n，看起来要占不少内存，但 n 在 10^5 级别时也就几 MB，完全没问题。

如果你追求极致空间，可以把最大值和最小值两个过程分开算，用两个函数复用同一对数组，把辅助数组压缩到两个。但这属于微优化，对比赛成绩没有实质影响，还是怎么不容易写错怎么来。

时间复杂度上有一个容易被忽略的点：虽然代码里有四段单调栈循环，但每个元素在每个循环里最多入栈一次、出栈一次，所以总操作次数是 O(n)，而不是 O(n^2)。这也是单调栈能扛住 10^5 数据的根本原因。

4.4 双周赛实战策略建议

这道题出现在 Q2，意味着它不应该消耗你太多时间。如果上场十分钟还没把“极差之和”这个模型识别出来，可能说明对“贡献法”这个套路还不够熟。建议赛前把力扣 2104、907、1856 这几道题刷一遍，它们共同构成了“子数组贡献 + 单调栈”的完整题单。

赛中如果真的没思路，我的保底策略是：先写一个 O(n^2) 暴力版本把样例过了，再对着暴力结果逐步改成 O(n) 版本。这样至少保证有分，不会因为一个空栈错误导致整题白给。不过这一策略只适合时间充裕的 Q2，到了 Q3 Q4 就别指望暴力能救你了。

我个人在实际操作中的体会是，这类“换皮题”在周赛里出现频率极高。出题人把“子数组范围和”改成“范围内总波动值”，本质就是把 max、min、sum 这几个词排列组合一下。你真正要训练的，不是背下某一题的标准答案，而是形成“看到所有子数组的某种统计量，立刻想到贡献法 + 单调栈”的条件反射。做到这一步，双周赛 Q2 基本就是送分题。