企业官网建设流程全解析

如果你也在刷题社区追过《每日一题》这类栏目，应该知道最折磨人的地方在哪：每天放出一道看起来不算超纲的题，题解敲出来也就十几行，但你自己想破头就是想不到那个关键的转折点。四月底这期又出了一道这样的题，标题五个字“换个角度思考”，等于把答案的钥匙提前亮出来了——可惜很多人看到题面后，还是先老老实实枚举子数组，然后被数据范围教做人。

今天这篇精讲，我就把这道题从头到尾拆给你看：为什么暴力不能碰，核心的“贡献法”是怎么把 O(n²) 降到 O(n) 的，单调栈在里面到底扮演什么角色，以及我实际写代码时踩过的几个坑。适合三类人读：准备校招笔试、正在刷题但卡在思维瓶颈、想彻底搞懂“枚举区间”类问题套路的同学。读完你不仅能写掉这题，以后遇到“所有子数组的最大值/最小值之和”这类变体，也能条件反射地换角度。

1. 先看题目：数遍所有子数组的最小值

1.1 题面与数据范围

题目大意是这样的：给定一个长度为 n 的数组 a，求所有非空连续子数组中最小值的和，最后对 10⁹+7 取模。

举个例子，数组是[3, 1, 2, 4]，所有连续子数组一共 10 个，把每个子数组的最小值列出来：

• 长度为 1：[3]→3，[1]→1，[2]→2，[4]→4
• 长度为 2：[3,1]→1，[1,2]→1，[2,4]→2
• 长度为 3：[3,1,2]→1，[1,2,4]→1
• 长度为 4：[3,1,2,4]→1

全部加起来：3 + 4 + 1×5? 不对，仔细数一下：3 出现 1 次，1 出现 6 次，2 出现 2 次，4 出现 1 次，总和 = 3 + 6 + 4 + 4 = 17。所以答案是 17。

数据范围是关键：n 最大能到 2×10⁵，a[i] 可以到 10⁹。出题人把数组长度拉到这个量级，就是在明示：凡是指数级、平方级的算法，基本不用往屏幕上打了。

1.2 暴力到底输在哪里

新手拿到这题，最自然的思路是三层循环：枚举左端点 l，枚举右端点 r，然后在[l, r]里扫一遍找最小值。这是 O(n³)，n 到 1000 就已经跑不动了。

稍微聪明一点的写法，是固定左端点，右端点不断向右扩展，同时用一个变量维护当前区间的最小值：

for (int l = 0; l < n; l++) { int mn = a[l]; for (int r = l; r < n; r++) { mn = min(mn, a[r]); ans += mn; } }

这是 O(n²)，n 等于 2×10⁵ 时，要执行约 2×10¹⁰ 次加法，按普通在线评测机每秒 10⁸ 次运算来算，跑完大概要几分钟到十几分钟，绝对超时。

很多同学到这里就卡住了：区间数量本身就接近 n²/2，就算能 O(1) 拿到任意区间的最小值，枚举所有区间也不可行。所以必须换一个思路——不是去优化“怎么更快地找最小值”，而是压根别枚举所有区间。

这就是标题“换个角度思考”的意思：不要从子数组出发，要从每个元素出发。

1.3 换个角度看：把求和拆给每个元素

如果我们把“所有子数组的最小值之和”拆开，其实可以等价地写成：

每个元素 a[i] 乘以“以 a[i] 作为最小值的子数组数量”，再把所有贡献加起来。

用生活里的话说：与其一个一个小组去查谁是分数最低的，不如反过来叫每个同学举手——你在多少个小组里是分数最低的那个？把这些人数乘以分数再加总，结果完全一样。

这里有一个前提：每个子数组的最小值可能有多个（元素值相同），所以必须约定一个归属规则，规定这个子数组的“最小值得分”算在哪个元素头上。比如规定“算给子数组里最右侧的那个最小值”。这样一来，每个子数组恰好被分给一个元素，不多不少，不重不漏。

于是问题从“枚举 n²/2 个子数组”变成了“对每个元素，数一数它左边能延伸多远、右边能延伸多远”，如果能快速求出来，总复杂度就能从 O(n²) 降到 O(n)。

2. 贡献法：核心公式与手算验证

2.1 左边借一步，右边借一步

对于每个位置 i，我们定义两个东西：

• left[i]：左侧第一个小于a[i] 的元素下标。如果不存在，记为 -1。
• right[i]：右侧第一个小于等于a[i] 的元素下标。如果不存在，记为 n。

为什么一个“小于”、一个“小于等于”？因为我们在上一节约定了“最小值得分算给最右侧的那个最小值”。这意味着：

• 向左延伸时，遇到值相同的元素，也要停下来，因为更左边的相同值才是更左侧子数组的最右侧最小值；
• 向右延伸时，遇到值相同的元素，同样要停下，因为对于跨过这两个相同值的区间，最右侧最小值不是你而是右边那个。

用公式写就是：以 a[i] 为最右侧最小值的子数组，左端点可以在(left[i], i]之间选，右端点可以在[i, right[i])之间选。所以数量是：

(i - left[i]) × (right[i] - i)

整个答案就是：

Σ a[i] × (i - left[i]) × (right[i] - i)，最后统一取模。

2.2 用 [3, 1, 2, 4] 完整手算一遍

这个例子刚才暴力算过，答案是 17。现在用贡献法重新推：

贡献相加：3 + 6 + 4 + 4 = 17，和前面暴力枚举的结果一模一样。

稍微解释下第一个数 3：下标 0 的 3，左边没有更小的元素，所以左端点只能取 0；右边第一个小于等于它的是下标 1 的 1，所以右端点也只能取 0。它只代表[3]这一个子数组，贡献 3×1=3。

下标 1 的 1 是全场最小的，左边没有比它小的，右边也没有比它小或等于它的（因为没有相等的），所以它横跨整个数组：左端点可以在 0 到 1 里选，共 2 种；右端点可以在 1 到 3 里选，共 3 种；2×3=6 个子数组都把 1 当作最右侧最小值，贡献 6×1=6。

2.3 重复元素为什么必须“一边严格一边非严格”

这是整个方法最容易翻车的地方。拿[2, 2, 2]举例。所有 6 个子数组的最小值都是 2，正确答案是 12。

如果left和right都用“严格小于”，也就是遇到相等的也继续往前走，会怎样？

• i=0：左边界 -1，右边界没有更小，按 3 算，子数组数量 1×3=3
• i=1：左边界 -1，右边界没有更小，子数组数量 2×3=6
• i=2：左边界 -1，右边界没有更小，子数组数量 3×3=9

加起来贡献是 (3+6+9)×2=36，远超真实答案 12。因为每个子数组被数了不止一次。

再试两边都用“小于等于”：

• i=0：左边界 -1，右边界 1，数量 1×1=1
• i=1：左边界 0，右边界 2，数量 1×1=1
• i=2：左边界 1，右边界 3，数量 1×1=1

贡献 (1+1+1)×2=6，又少了。因为某些子数组没人认领。

只有“左侧严格小于、右侧小于等于”，也就是把最小值都归给最右侧的最小值时：

• i=0：left=-1，right=1，数量 1×1=1，贡献 2
• i=1：left=-1，right=2，数量 2×1=2，贡献 4
• i=2：left=-1，right=3，数量 3×1=3，贡献 6

总和 12，正好。

这三个 2 各自认领的子数组是：下标 0 只认领[0]；下标 1 认领[0,1]和[1]；下标 2 认领[0,1,2]、[1,2]和[2]。6 个子数组，一个不重，一个不漏。

所以写代码前，先把这条规则刻在脑子里：你想把相同最小值归给哪一侧，就把另一侧的边界条件设为严格不等。这道题归给最右侧，所以右侧遇到相等的就停，左侧遇到相等的也要停（因为左侧相等的元素哪怕在区间里，也不影响你这个“最右侧最小值”的称号，但左端点一旦越过它，最右侧最小值就不是你了）。

3. 单调栈：线性时间内找到每个数的边界

3.1 为什么选单调栈而不是别的

现在问题变成：对 n 个位置，都要找到左侧第一个小于自己的位置，以及右侧第一个小于等于自己的位置。朴素做，每个位置往左右两边扫，最坏 O(n²)。我们需要 O(n) 或 O(n log n)。

有人可能先想到线段树二分、RMQ 二分，但这类做法写起来麻烦，而且常数不小。这题的最佳选择是单调栈：每个元素最多入栈一次、出栈一次，整体 O(n)，线性扫一遍就能把left和right同时算出来。

单调栈的直觉可以这么理解：你维护一个栈，栈里的元素都是“还没确定右边界”的候选人。新来的元素 i 比某些候选人更小或相等，那么这些候选人的右边界就是 i 了——它们已经没有机会在更靠右的区间里继续当最小值了，该出栈领奖。剩下的栈顶，自然就是当前元素左侧第一个比它小的位置。

这就像一个队列里找前面第一个比自己矮的人：新来的人如果比排队的某些人矮，那些人就被“淘汰”并确定了自己的右边关卡；新来的人前面的那个还没被淘汰的，就是它左边第一个比自己矮的。

3.2 一次遍历同时算出 left 和 right

声明两个数组，left初始化为 -1，right初始化为 n。

从左到右扫描 i = 0, 1, ..., n-1，重复以下操作：

1. 当栈非空且a[栈顶] >= a[i]时：
   • right[栈顶] = i，表示栈顶元素的右侧第一个小于等于它的边界是 i；
   • 弹出栈顶。
2. 如果此时栈非空，left[i] = 栈顶；否则left[i] = -1。
3. 把 i 压入栈。

这一步很关键：弹出条件用了>=，所以被弹出的元素遇到的是“小于等于”自己的右边界；留在栈里的栈顶一定严格小于a[i]，所以left[i]是“严格小于”的左边界。一条规则，两个边界，全对上了。

用 [3, 1, 2, 4] 手推一遍：

• i=0，a=3：栈空，left[0]=-1，压入 0。
• i=1，a=1：栈顶 0 的值为 3，3>=1，所以 right[0]=1，弹出；栈空，left[1]=-1，压入 1。
• i=2，a=2：栈顶 1 的值为 1，1>=2 不成立，left[2]=1，压入 2。
• i=3，a=4：栈顶 2 的值为 2，2>=4 不成立，left[3]=2，压入 3。

最后 right[1]、right[2]、right[3] 保持初始值 4。结果正是我们表格里用的那组数。

用 [2, 2, 2] 手推：

• i=0：栈空，left[0]=-1，压入 0。
• i=1：栈顶 0 值 2，2>=2，right[0]=1，弹出；栈空，left[1]=-1，压入 1。
• i=2：栈顶 1 值 2，2>=2，right[1]=2，弹出；栈空，left[2]=-1，压入 2。

right[2] 保持 3。和之前验证的结果一致。

3.3 为什么每个元素只进出栈一次

这是单调栈复杂度的关键。每个下标在扫描过程中最多被压入栈一次，也最多因为触发>=条件被弹出一次。一旦弹出，它的right就被确定，之后再也不会进栈。所以虽然while循环看着可能连续弹很多个，但所有元素加起来的弹出次数最多是 n 次，整体复杂度 O(n)。

相比之下，暴力枚举子数组是 O(n²)，核心区别就在于：暴力把每个区间都当独立问题处理，而单调栈把 n 个元素各自“管辖区间”一次性算完，区间之间的重叠信息被压缩进了栈的淘汰过程里。

4. 完整代码与执行细节

4.1 可直接运行的 C++ 解法

#include <bits/stdc++.h> using namespace std; const int MOD = 1e9 + 7; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } vector<int> left(n, -1), right(n, n); vector<int> st; st.reserve(n); for (int i = 0; i < n; i++) { while (!st.empty() && a[st.back()] >= a[i]) { right[st.back()] = i; st.pop_back(); } left[i] = st.empty() ? -1 : st.back(); st.push_back(i); } long long ans = 0; for (int i = 0; i < n; i++) { long long cnt = 1LL * (i - left[i]) * (right[i] - i); ans = (ans + cnt % MOD * a[i]) % MOD; } cout << ans << '\n'; return 0; }

这段代码是我在实际提交前反复验证过的版本，核心逻辑就是第三节的一次遍历。代码里值得注意的细节有三个。

第一，栈里存的是下标，不是值。因为最后计算(i - left[i]) * (right[i] - i)需要下标做差，如果只存值等于白算。

第二，所有区间数量相乘用1LL强转，避免 int 溢出。(i - left[i])和(right[i] - i)都可能到 n 的量级，两者相乘最大接近 n²/4，n 取 2×10⁵ 时大约 10¹⁰，int 根本装不下。

第三，取模时先让cnt % MOD再乘a[i]。cnt本身已经用 long long 存了，不取模直接乘也问题不大，但先取模能让后续乘法更小，养成习惯没坏处。

4.2 边界情况自查清单

写完代码别急着交，先看几个边界：

• n=1：只有一个元素，left[0]=-1，right[0]=n=1，数量 (0-(-1))×(1-0)=1，答案就是 a[0]，正确。
• 数组严格递增，比如 [1, 2, 3, 4]：每个元素的左边界都是前一个元素，right 全是 n，数量分别是 1、2、3、4。对应子数组分别以 1、2、3、4 作为最小值，总和 = 1×1? 实际算一下就知道没问题。
• 数组严格递减，比如 [4, 3, 2, 1]：每个新元素都会弹掉前面所有元素，right 会依次指向后面位置，left 全是 -1。这样 4 只管 [4]，3 管 [4,3] 和 [3]，2 管 [4,3,2]、[3,2]、[2]，1 管全部，组合起来正好覆盖所有子数组。
• 全相等的数组，比如 [5, 5, 5]：必须按第三节约定的“最右侧最小值”归属，数量是 1、2、3，总和 = 6×5=30。只要弹出条件写的是>=，这个结果自动成立。

4.3 对拍验证：新手最容易忽略的效率工具

单调栈这类代码，逻辑上一旦想错，小数据可能侥幸通过，大数据直接崩，或者答案差一点但看不出来。我强烈建议写一个暴力函数做对拍：

long long brute(vector<int>& a) { int n = a.size(); long long res = 0; for (int l = 0; l < n; l++) { int mn = a[l]; for (int r = l; r < n; r++) { mn = min(mn, a[r]); res += mn; } } return res; }

然后在本地生成 n 在 1 到 10 之间的随机数组，把暴力结果和单调栈结果对比。n 小的时候暴力很快，可以对拍成千上万组。对拍通过之后再放大数据测性能。

我在实际刷题时，遇到这种公式推导型题目，对拍是必经步骤：先用暴力锁定答案，再验证优化做法的正确性。不要小看这一步，很多“自以为懂了”的边界错误，都是对拍拍出来的。

5. 常见问题与排查技巧实录

5.1 高频问题速查表

5.2 我踩过的坑

第一次写这题时，我把弹出条件写成了>，也就是遇到相等不弹出。当时想的是“相等也是最小值，应该都能算”，结果[2,2,2]跑出来答案 36，多了三倍。排查半天才发现是相等的归属问题。

后来我把边界规则用注释写在代码前面：

// 左侧第一个小于 a[i]：left[i] // 右侧第一个小于等于 a[i]：right[i] // 相等元素归给右边，子数组按最右侧最小值认领

写注释这个习惯帮了我大忙。因为这种规则很容易在调试中忘掉，注释等于把思维模型固化成代码旁边的提醒。

还有一个坑是关于right数组的初始化。很多人把right初始成 0，认为反正后面会赋值。问题在于不是每个元素都会被弹出，比如数组里的最后一个元素、或者右侧没有更小元素的元素，它们会一直留在栈里直到循环结束。如果right初始值不是 n，最后计算区间时就会出现负数长度。所以right的初始值必须是 n，这代表“右侧没有更小的，可以一直延伸到数组末尾”。

5.3 什么时候不推荐用这招

“贡献法 + 单调栈”不是万能钥匙。如果题目只是问单个区间的最小值，那是 RMQ 或线段树的问题，不需要算每个元素的管辖区间。如果 n 很小，比如 n ≤ 5000，O(n²) 的暴力写法反而更简单直观，代码出错概率低。如果数组里要同时维护修改操作，那单调栈就失效了，应该去想想线段树。

换句话说，当你发现题目要枚举所有区间，且 n 在 10⁵ 以上，区间信息又不能简单合并时，贡献法就是第一候选。这个判断本身也是一种“换个角度思考”。

6. 换角度思考的迁移：这招还能用在哪

把这题吃透之后，你会发现“把区间统计拆给单个元素”是算法竞赛和面试笔试里非常高频的思维模式。我至少在三类经典问题上见过它的影子。

第一类是“所有子数组最大值之和”。做法几乎一模一样，只需要把边界规则反过来：找左侧第一个大于自己的、右侧第一个大于等于自己的，贡献公式不变。等于说同一套单调栈模板，改两行判断条件就又是一道题。

第二类是“最大矩形面积”。给一个柱状图，找面积最大的矩形，本质上也是每一根柱子向左右找到第一个比自己矮的柱子，然后用高度乘以宽度更新答案。不少人第一次看那题觉得玄学，其实底层逻辑和这题完全同构：每个矩形的高度由最低的那根柱子决定，换成贡献法的语言，就是每根柱子作为“最低点”能撑起多大跨度。

第三类是更广义的“差分、前缀和”思想。比如区间加问题，如果把每个区间的贡献累加到每个点上是 O(n²)，但转化成在区间端点记录增量，一次前缀和还原，就变成 O(n)。这同样是“不从区间出发，从端点出发”的换角度。

我在刷题过程中养成了一个习惯：读完题先花两分钟估算暴力复杂度。如果明显超时，就追问自己一句——“能不能让每个位置回答一个问题？”这道题里，每个位置回答的是“你有多少个以你为最右侧最小值的子数组”。想通这一句，代码反而是最后十分钟的事。

如果你第一次接触这个思路没转过来，不用沮丧。这类“贡献法”题第一次见都会觉得绕，但一旦亲手推过两三个例子，再写一次单调栈，下次看到“所有子数组的某个统计”就会自动想到：别枚举区间，让每个元素自己举手。