有效子数组数量：从暴力枚举到单调栈O(n)解法

如果你以为“有效子数组的数量”只是一道简单的双重循环题，那可能有点低估它了。这道LintCode 3866题在很多面试和刷题群里都出现过，函数签名public int validSubarrays(int[] nums)摆在那里——输入一个整型数组，返回满足条件的连续子数组数量。题目的核心定义很常见：一个连续子数组被称为有效的，当且仅当它的第一个元素不大于该子数组中的其他元素，换句话说，每个有效子数组必须以自己范围内的最小值开头。让AI助手来分析这种题，它第一句话一定也是反问：你确定“有效”的边界是什么？边界一旦明确，解法其实非常固定。这篇文章写给正在准备面试、尤其是对单调栈和贡献法还不太熟的同学，我会从暴力解法一路讲到O(n)的单调栈实现，把等值元素处理、边界条件、溢出问题这些容易翻车的细节全部拆开讲透。

1. 题目到底在问什么：先别急着写循环

1.1 子数组的边界与“首元素最小”约束

数组里的子数组一定是要连续的，这和子序列不同。比如[3,1,2]中，[3,1]是子数组，[3,2]不是，因为3到2中间隔了一个1，并不连续。一个长度为n的数组，子数组总数是n*(n+1)/2，这个公式后面会反复用到。

现在加上“有效”这个条件：子数组的第一个元素必须不大于子数组内的所有元素。换句话说，nums[i]要满足：

• 它是所在子数组的最小值；
• 允许与其他元素相等，因为“不大于”是小于或等于。

我用[3,1,2]举例，把所有子数组列出来看哪些有效：

所以[3,1,2]的答案是4。注意一个容易混淆的点：有效子数组并不要求这个子数组是整个数组前缀或者后缀，它可以是任何一段连续的区间。

1.2 暴力解法的两种形态

面对这种计数题，第一反应一定是枚举。最简单的是三重循环版本：枚举左端点i，枚举右端点j，再枚举k从i到j检查nums[i]是否是区间最小值。

public int validSubarrays(int[] nums) { int n = nums.length; int ans = 0; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { boolean valid = true; for (int k = i; k <= j; k++) { if (nums[k] < nums[i]) { valid = false; break; } } if (valid) { ans++; } } } return ans; }

这个写法正确性没问题，但时间复杂度是O(n^3)，数组长度过100基本就卡死了。

其实稍加观察可以发现，检查区间最小值不一定要每次从头扫。固定左端点i之后，只要向右扩展过程中一直没有遇到比nums[i]更小的元素，当前区间就一定有效。于是一个更聪明的暴力版本是：固定起点i，不断向右移动j，一旦碰到nums[j] < nums[i]就立刻停止。这样每个起点单独扩展，时间复杂度是O(n^2)。

public int validSubarrays(int[] nums) { int n = nums.length; int ans = 0; for (int i = 0; i < n; i++) { int j = i; while (j < n && nums[j] >= nums[i]) { j++; } ans += j - i; } return ans; }

这段代码其实已经非常接近最优解了。它的核心逻辑是：以i为起点，右边第一个比nums[i]小的位置记为j，那么i能贡献的有效子数组数量正好是j - i。现在的问题只有一个：如果每个起点都用while往后扫，遇到类似[1,2,3,4,5]这种递增数组，每个起点都要扫到末尾，一下子又退化成O(n^2)。我们需要更快地求出每个i对应的j。

2. 单调栈优化：找到每个起点能延伸多远

2.1 关键观察：右边第一个更小元素就是终点禁区

把1.2的思路抽象成数学表达，定义R[i]为i右侧第一个满足nums[R[i]] < nums[i]的下标，如果不存在则R[i] = n。那么以i为起点的有效子数组，它的右端点可以取i到R[i] - 1之间的任意位置，数量就是R[i] - i。

为什么是“第一个”更小的位置？因为只要右端点跨过R[i]，nums[R[i]]在子数组内且比nums[i]小，首元素就不再是区间最小值，子数组立刻失效。而在R[i]之前的所有元素都满足nums[k] >= nums[i]，所以任意右端点j（i <= j < R[i]）都能保证nums[i]是区间内最小值。

继续用[3,1,2]验证：

• i=0，nums[0]=3，右边第一个比3小的是下标1，R[0]=1，贡献1；
• i=1，nums[1]=1，右边没有比1更小的元素，R[1]=3，贡献3-1=2；
• i=2，nums[2]=2，右边没有比2更小的元素，R[2]=3，贡献1。

总和是1+2+1=4，和暴力枚举结果一致。所以问题彻底转化成了：高效求出每个元素的右边第一个更小元素下标。这正是单调栈的经典应用场景。

2.2 单调递增栈的求法

求右边第一个更小元素，套路是从左到右遍历数组，维护一个下标栈，要求栈底到栈顶的元素值严格递增。每遍历到一个新元素nums[i]，就检查栈顶：

• 如果栈顶元素比nums[i]大，说明nums[i]就是栈顶元素右边第一个更小的值，于是弹出栈顶并记下它的R值等于i；
• 继续检查新的栈顶，直到栈为空或者栈顶元素不大于nums[i]；
• 然后把i压入栈。

为什么栈底到栈顶要保持递增？因为如果栈顶上方压着一个更小的元素，那么下方元素右侧第一个更小值应该优先看这个更小的栈顶，而不是等未来的元素来触发，逻辑会乱。单调栈本质上是在维护一个“还没有找到右侧更小点”的候选集合，集合内部元素按值从下到上递增。新元素只要比栈顶小，就直接解决了栈顶的疑问。

这个过程保证每个下标最多入栈一次、出栈一次，所以总时间复杂度是O(n)。栈中剩余元素说明右侧没有更小值，R保持为数组长度n。

2.3 相等的坑：严格小于还是小于等于

这里最容易踩坑。因为题目要求“不大于”，所以nums[k] == nums[i]时子数组依然有效。这意味着右边第一个“更小”必须是严格小于，相等不能作为终止边界。

我见过很多人把判断写成nums[i] <= nums[stack.peek()]，结果全相等数组[2,2,2]直接返回3，正确答案应该是6。原因很简单：如果用小于等于触发弹栈，那么第二个2会把第一个2弹出，并把R[0]记为1，于是第一个2贡献的子数组数量只有1，丢失了[2,2]和[2,2,2]这两个有效答案。

正确的弹栈条件必须是：

nums[i] < nums[stack.peek()]

也就是只有当新元素严格小于栈顶元素时，栈顶的右侧更小值才真正出现。遇到相等元素时，新的元素应该压在旧元素上方，让旧元素继续等待右边更小的值出现。这个细节一旦记错，丧心病狂的全等数组测试用例会立刻暴露问题。

3. 完整实现与手把手推演

3.1 可直接提交的Java代码

综合前面的推导，我给出第一版可以直接提交的实现。为了不在提交时因为import顺序手忙脚乱，我用全限定名写Java标准库类，这样复制到任何OJ环境都能编译。

public class Solution { public int validSubarrays(int[] nums) { int n = nums.length; int[] right = new int[n]; java.util.Arrays.fill(right, n); java.util.Deque<Integer> stack = new java.util.ArrayDeque<>(); for (int i = 0; i < n; i++) { while (!stack.isEmpty() && nums[i] < nums[stack.peek()]) { right[stack.pop()] = i; } stack.push(i); } long ans = 0; for (int i = 0; i < n; i++) { ans += right[i] - i; } return (int) ans; } }

这段代码的逻辑分两步：第一步用单调栈求出所有right数组；第二步累加每个位置的贡献。right[i]代表i右侧第一个严格小于nums[i]的下标，如果不存在就保持初始值n。

3.2 模拟一遍栈的变化

理论讲再多不如手推一遍。我用[3,1,2]来完整模拟：

遍历结束后栈内还有[1,2]，它们右侧没有更小元素，因此right[1]和right[2]保持初始值3。最终：

• ans = right[0]-0 + right[1]-1 + right[2]-2
• ans = (1-0) + (3-1) + (3-2) = 1+2+1 = 4

答案正确。

再测一个所有元素相等的例子[2,2,2]：

ans = (3-0)+(3-1)+(3-2)=3+2+1=6。全等数组中所有子数组都有效，因为首元素与后面的元素相等，满足“不大于”，6个结果一点不少。

3.3 复杂度、边界与int溢出

这个解法的单调栈部分每个元素至多入栈一次、出栈一次，整体是O(n)时间，right数组占用O(n)空间。对于n=10^5的输入，运行时间非常稳定，实测一般几毫秒到十几毫秒。

边界条件需要检查几类特殊情况：

• 空数组：n=0，right长度为0，循环不执行，ans=0，返回0，没问题。
• 单元素数组：[x]，right[0]=n=1，ans=1，有效，没问题。
• 严格递减数组[5,4,3]：每个元素的right都是它的下一个位置，right=[1,2,3]，ans=1+1+1=3，只有三个单元素子数组有效，没问题。
• 严格递增数组[1,2,3]：right全为3，ans=3+2+1=6，所有子数组都有效，没问题。

int溢出是个容易忽略的点。n如果达到10^5，理论上最大答案是5*10^9，已经超过int上限。虽然题目把方法签名定成返回int，通常意味着测试数据保证结果不溢出，但稳妥起见，我在累加时用了long，最后再强转回int。这是很实用的小习惯，能在一些数据范围刁钻的题目上避免莫名其妙的WA。

3.4 进阶写法：不存数组，弹出时直接累加

right数组版本很好理解，但还可以更省空间。因为每个元素出栈时，它的right值已经确定了，此时可以直接把贡献算进答案，不需要先把right存下来再算第二遍。

public int validSubarrays(int[] nums) { int n = nums.length; long ans = 0; java.util.Deque<Integer> stack = new java.util.ArrayDeque<>(); for (int i = 0; i < n; i++) { while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) { int idx = stack.pop(); ans += i - idx; } stack.push(i); } while (!stack.isEmpty()) { int idx = stack.pop(); ans += n - idx; } return (int) ans; }

这里注意弹栈条件写成了nums[stack.peek()] > nums[i]，与第一版的nums[i] < nums[stack.peek()]本质相同。每次弹出下标idx时，当前i就是idx右侧第一个更小元素，所以以idx为起点的有效子数组右端点可以在[idx, i-1]之间取，共i-idx个。遍历结束后栈里剩下的下标右侧没有更小元素，每个贡献n-idx。

这个写法少了一个right数组，代码也更短，面试时写起来更顺畅。我个人更推荐这一版，但前提是你已经理解right数组版本的含义，不然容易变成背代码。

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

4.1 栈里剩余元素忘处理

用第二种写法时，最常犯的错是遍历结束后忘了清空栈。如果直接返回ans，栈里剩余的下标全部丢失。比如[3,1,2]中，遍历结束时栈里还有下标1和2，它们分别对应贡献2和1，忘掉的话ans只有1，正确答案4直接砍半。

用right数组版本的话这个问题不明显，因为right数组初始值n天然处理了剩余下标，但进阶写法要求你记得那个收尾while循环。我的经验是：写完后立刻检查一下栈，问自己“栈里还剩什么”，宁可多写几行也不能丢。

4.2 误用Stack类导致性能退化

Java里java.util.Stack虽然也叫栈，但它继承了Vector，所有方法都带同步锁，在这种高频入栈出栈的场景下性能比ArrayDeque差一截。刷题面试时优先用ArrayDeque，它没有锁，底层数组扩容策略也友好一些。

如果不想写全限定名，可以在文件顶部加一行import java.util.ArrayDeque;。我见过有人因为纠结import放在哪里结果编译报错，索性用全限定名，一劳永逸。

4.3 right数组默认值没设对

如果用right数组版本，必须先用Arrays.fill(right, n)把默认值填成n。很多人下意识用new int[n]，默认值全是0，那么对于没有右侧更小元素的下标，right[i]会错误地变成0，贡献变成负数。特别是递增数组，全被0污染，结果直接负得离谱。

如果不填n，也可以在遍历结束后再遍历栈，把栈里剩余下标的right值逐个设为n。两种方式等价，但预设n明显更简洁。

4.4 用暴力对拍验证单调栈写错没有

单调栈这类题，边界条件多，等值处理又容易错，光靠脑内推理很难保证一遍过。我强烈建议写一个暴力版本，然后用小数组随机测试，对拍验证：

• 固定种子随机生成数组；
• 对比暴力O(n^2)版本和单调栈版本的结果；
• 一旦不一致，打印数组和两个结果。

实际排查的时候，优先看全相等数组、递增数组、递减数组、随机含重复值数组这四类用例。很多隐藏bug在随机用例中不一定能触发，但规模小、元素值相同的用例很容易暴露问题。

4.5 一个容易被忽略的返回类型细节

方法签名返回int，但前面强调过答案可能超过int。如果你在lint代码时把ans直接定义成int，n较大时可能溢出成负数，表面看是算法问题，实际是类型问题。养成累加用long的习惯，最后转int即可。

还有一个小细节：如果题目要求方法放在Solution类里，类名拼写错了会直接编译错误。这种错误看似低级，但在紧张刷题时真的会发生，提交前扫一眼类名和方法名。

5. 从这道题看一类子数组计数问题

5.1 贡献法的本质

很多子数组计数问题看起来都需要枚举区间，但通过“固定一个端点、看另一个端点的取值范围”可以把二维枚举压成一维计算。这道题里，固定左端点后，右端点能取的范围由右边第一个更小元素决定。每个起点贡献的区间互不重叠，最终总数就是各个起点的贡献和。这种思路就是贡献法，也叫“按起点统计法”。

如果用生活化类比来解释：一个班级要选出以某个人为“班内最小”的连续小组，只要知道右边第一个比这个人更小的人站在哪里，组队时就不能跨过那个位置。每个“起点同学”能组建多少小组只取决于那个挡在他前面的更小值，不需要把所有小组都枚举一遍。

5.2 变体一：统计每个子数组最小值之和

这类题的经典变体是：给定数组，求出所有连续子数组的最小值之和。暴力枚举所有子数组求最小值是O(n^2)，但利用单调栈可以O(n)解决。思路是为每个元素找左右两侧第一个更小元素的位置，从而算出以该元素为最小值的子数组有多少个，再把nums[i]乘以数量累加。

和本题的区别在于：题目只要求起点是最小值，变体则要求最小值可以出现在任意位置。所以变体需要同时求左边边界和右边边界，用乘法计算左右端点组合数。理解了本题的起点贡献法，再看这类变体就不会觉得突兀。

5.3 变体二：最大矩形面积

单调栈另一道经典应用是柱状图中最大矩形面积。给定一组柱子高度，求能勾勒出的最大矩形面积。核心是对于每根柱子，找左右两侧第一根比它矮的柱子，高度乘以宽度就是该柱子作为最低点时的最大矩形候选答案。

你会发现这些题的骨架完全一致：找左右更近的较小元素，然后用位置差算贡献或算面积。骨架相同，细节不同，这就是为什么我一直建议把单调栈模板理解透而不是死记。

5.4 怎么判断该不该用单调栈

我的判断信号通常有三个：

• 题目涉及数组，并且要求找“第一个比当前元素大/小”的位置；
• 题目统计子数组数量、区间贡献，且贡献与区间最值有关；
• 暴力解法里存在大量连续、重复的比较，肉眼可见可以复用信息。

满足其中任意两条，就可以优先尝试单调栈。当然，不是说所有这类题都一定用单调栈，滑窗、线段树也可能派上用场，但单调栈是最值得先手写出来的方案。

我自己的刷题习惯是，看到“数组 + 子数组数量 + 最值约束”三个关键词同时出现，先默认往单调栈方向想，但一定先写一个暴力版本验证自己对“有效”的理解没有偏。很多WA不是因为单调栈写错，而是题目定义理解偏了。等值元素到底是严格小于还是小于等于，就是最典型的例子。

这道题整体难度不算高，但它把单调栈、贡献法、边界处理三个知识点浓缩在一起，非常值得练手。如果你刚开始接触这类题，先把暴力版写对，再用栈优化，最后把[2,2,2]、[5,4,3]、[1,2,3]这几个用例全部跑一遍，手感很快就会上来。后面再遇到子数组统计类问题时，你大概率一眼就能看出它想考什么。