如果你也在刷题社区追过《每日一题》这类栏目应该知道最折磨人的地方在哪每天放出一道看起来不算超纲的题题解敲出来也就十几行但你自己想破头就是想不到那个关键的转折点。四月底这期又出了一道这样的题标题五个字“换个角度思考”等于把答案的钥匙提前亮出来了——可惜很多人看到题面后还是先老老实实枚举子数组然后被数据范围教做人。今天这篇精讲我就把这道题从头到尾拆给你看为什么暴力不能碰核心的“贡献法”是怎么把 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。现在用贡献法重新推ia[i]left[i]right[i](i-left[i])(right[i]-i)子数组数量贡献03-11111311-1423662214122434241114贡献相加3 6 4 4 17和前面暴力枚举的结果一模一样。稍微解释下第一个数 3下标 0 的 3左边没有更小的元素所以左端点只能取 0右边第一个小于等于它的是下标 1 的 1所以右端点也只能取 0。它只代表[3]这一个子数组贡献 3×13。下标 1 的 1 是全场最小的左边没有比它小的右边也没有比它小或等于它的因为没有相等的所以它横跨整个数组左端点可以在 0 到 1 里选共 2 种右端点可以在 1 到 3 里选共 3 种2×36 个子数组都把 1 当作最右侧最小值贡献 6×16。2.3 重复元素为什么必须“一边严格一边非严格”这是整个方法最容易翻车的地方。拿[2, 2, 2]举例。所有 6 个子数组的最小值都是 2正确答案是 12。如果left和right都用“严格小于”也就是遇到相等的也继续往前走会怎样i0左边界 -1右边界没有更小按 3 算子数组数量 1×33i1左边界 -1右边界没有更小子数组数量 2×36i2左边界 -1右边界没有更小子数组数量 3×39加起来贡献是 (369)×236远超真实答案 12。因为每个子数组被数了不止一次。再试两边都用“小于等于”i0左边界 -1右边界 1数量 1×11i1左边界 0右边界 2数量 1×11i2左边界 1右边界 3数量 1×11贡献 (111)×26又少了。因为某些子数组没人认领。只有“左侧严格小于、右侧小于等于”也就是把最小值都归给最右侧的最小值时i0left-1right1数量 1×11贡献 2i1left-1right2数量 2×12贡献 4i2left-1right3数量 3×13贡献 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初始化为 -1right初始化为 n。从左到右扫描 i 0, 1, ..., n-1重复以下操作当栈非空且a[栈顶] a[i]时right[栈顶] i表示栈顶元素的右侧第一个小于等于它的边界是 i弹出栈顶。如果此时栈非空left[i] 栈顶否则left[i] -1。把 i 压入栈。这一步很关键弹出条件用了所以被弹出的元素遇到的是“小于等于”自己的右边界留在栈里的栈顶一定严格小于a[i]所以left[i]是“严格小于”的左边界。一条规则两个边界全对上了。用 [3, 1, 2, 4] 手推一遍i0a3栈空left[0]-1压入 0。i1a1栈顶 0 的值为 331所以 right[0]1弹出栈空left[1]-1压入 1。i2a2栈顶 1 的值为 112 不成立left[2]1压入 2。i3a4栈顶 2 的值为 224 不成立left[3]2压入 3。最后 right[1]、right[2]、right[3] 保持初始值 4。结果正是我们表格里用的那组数。用 [2, 2, 2] 手推i0栈空left[0]-1压入 0。i1栈顶 0 值 222right[0]1弹出栈空left[1]-1压入 1。i2栈顶 1 值 222right[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; vectorint a(n); for (int i 0; i n; i) { cin a[i]; } vectorint left(n, -1), right(n, n); vectorint 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²/4n 取 2×10⁵ 时大约 10¹⁰int 根本装不下。第三取模时先让cnt % MOD再乘a[i]。cnt本身已经用 long long 存了不取模直接乘也问题不大但先取模能让后续乘法更小养成习惯没坏处。4.2 边界情况自查清单写完代码别急着交先看几个边界n1只有一个元素left[0]-1right[0]n1数量 (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×530。只要弹出条件写的是这个结果自动成立。4.3 对拍验证新手最容易忽略的效率工具单调栈这类代码逻辑上一旦想错小数据可能侥幸通过大数据直接崩或者答案差一点但看不出来。我强烈建议写一个暴力函数做对拍long long brute(vectorint 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 高频问题速查表现象原因解决方案答案比真实值大很多左右边界的“等于”处理不一致导致同一子数组被多个元素重复认领明确归属规则建议左侧严格小于、右侧小于等于弹出条件用答案比真实值小边界定得太紧部分子数组没分给任何元素检查两个方向是否都正确取到了应该停的位置大样例答案溢出乘法结果超过 int 范围用 long long注意先取模再乘结果偶尔错、小数据却全对大概率是边界条件在特殊数据上才暴露用全相等、严格递增、严格递减三组数据测试时间超时可能栈里存值而非下标或者用了非单调栈做法确认每个元素只入栈出栈一次整体 O(n)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 ≤ 5000O(n²) 的暴力写法反而更简单直观代码出错概率低。如果数组里要同时维护修改操作那单调栈就失效了应该去想想线段树。换句话说当你发现题目要枚举所有区间且 n 在 10⁵ 以上区间信息又不能简单合并时贡献法就是第一候选。这个判断本身也是一种“换个角度思考”。6. 换角度思考的迁移这招还能用在哪把这题吃透之后你会发现“把区间统计拆给单个元素”是算法竞赛和面试笔试里非常高频的思维模式。我至少在三类经典问题上见过它的影子。第一类是“所有子数组最大值之和”。做法几乎一模一样只需要把边界规则反过来找左侧第一个大于自己的、右侧第一个大于等于自己的贡献公式不变。等于说同一套单调栈模板改两行判断条件就又是一道题。第二类是“最大矩形面积”。给一个柱状图找面积最大的矩形本质上也是每一根柱子向左右找到第一个比自己矮的柱子然后用高度乘以宽度更新答案。不少人第一次看那题觉得玄学其实底层逻辑和这题完全同构每个矩形的高度由最低的那根柱子决定换成贡献法的语言就是每根柱子作为“最低点”能撑起多大跨度。第三类是更广义的“差分、前缀和”思想。比如区间加问题如果把每个区间的贡献累加到每个点上是 O(n²)但转化成在区间端点记录增量一次前缀和还原就变成 O(n)。这同样是“不从区间出发从端点出发”的换角度。我在刷题过程中养成了一个习惯读完题先花两分钟估算暴力复杂度。如果明显超时就追问自己一句——“能不能让每个位置回答一个问题”这道题里每个位置回答的是“你有多少个以你为最右侧最小值的子数组”。想通这一句代码反而是最后十分钟的事。如果你第一次接触这个思路没转过来不用沮丧。这类“贡献法”题第一次见都会觉得绕但一旦亲手推过两三个例子再写一次单调栈下次看到“所有子数组的某个统计”就会自动想到别枚举区间让每个元素自己举手。