LeetCode 907. 子数组的最小值之和
题目描述
题意分析
求所有非空连续子数组的最小值之和，最后对 $10^9 + 7$ 取模。子数组有 $O(n^2)$ 个，逐个枚举并维护最小值仍需要平方级时间，难以处理长度为 $3 \times 10^4$ 的数组。
可以把求和顺序反过来：不再逐个子数组找最小值，而是统计每个元素作为最小值时负责多少个子数组，再累加它的贡献。一个子数组可能有多个相同的最小值，必须先约定只归其中一个位置负责。
解法：单调栈统计元素贡献
核心思路
[!blue]
约定每个子数组归它最右侧的最小值负责。对位置
i，左端点可以越过与arr[i]相等的元素，但不能越过更小的元素；右端点既不能越过更小的元素，也不能包含与arr[i]相等的元素，否则负责该子数组的就应是右边那个位置。因此令
L = prevLess[i]为左侧最近的严格更小元素下标，R = nextLessEqual[i]为右侧最近的小于等于元素下标。不存在时分别取-1、n。位置i负责的子数组恰好满足L < left <= i <= right < R：左端点有i - L种选择，右端点有R - i种选择，两者可以独立组合，贡献为arr[i] * (i - L) * (R - i)。这些范围保证子数组中没有比
arr[i]更小的值，并且它右侧没有相等值，所以i确实是最右侧最小值。反过来，任意子数组的最右侧最小值也一定满足这两个边界限制。因此所有子数组都会被统计一次，不会重复或遗漏。用单调栈求左边界时，从左向右扫描，栈存下标，所对应的值从栈底到栈顶严格递增。遇到
arr[i]，弹出所有大于等于它的栈顶：这些位置不可能是当前的严格更小边界；对将来的位置而言，i比它们更近、值又不大于它们，它们也不可能再成为最近的严格更小候选。弹出后留下的栈顶，就是当前左侧最近的严格更小位置。清栈后从右向左同样处理右边界，但只弹出严格大于
arr[i]的值，保留相等值作为阻挡右端点的边界。两个方向的弹栈条件一严一松，正好实现前面规定的归属规则，而不是为了维护栈随意选择的条件。最后遍历每个位置累加贡献。左右距离与元素值相乘可能超出 32 位整数，应在乘法之前使用
long或int64；逐次取模不会改变最终答案的余数。
解题步骤
- 从左向右扫描。弹出所有值大于等于
arr[i]的下标，栈顶就是左侧第一个严格更小的位置。- 清空栈，从右向左扫描。弹出所有值严格大于
arr[i]的下标，栈顶就是右侧第一个小于等于它的位置。- 对每个
i计算左右端点的选择数，相乘后再乘arr[i]，累加时使用 64 位整数并取模。
-1和n是数组外的边界，不需要真的入栈；它们让两端元素仍能直接使用同一个距离公式。只有一个元素时，左右选择数都为1；大量元素相等时，不对称边界仍会把每段子数组唯一分配给其最右侧位置。
代码实现
class Solution {
private static final int MOD = 1_000_000_007;
public int sumSubarrayMins(int[] arr) {
int n = arr.length;
int[] prevLess = new int[n];
int[] nextLessEqual = new int[n];
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
stack.pop();
}
// 左界严格更小，允许左侧相等值纳入当前元素负责的区间。
prevLess[i] = stack.isEmpty() ? -1 : stack.peek();
stack.push(i);
}
stack.clear();
for (int i = n - 1; i >= 0; i--) {
while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
stack.pop();
}
// 右界保留相等值，一严一松把重复最小值的区间交给最右者。
nextLessEqual[i] = stack.isEmpty() ? n : stack.peek();
stack.push(i);
}
long ans = 0;
for (int i = 0; i < n; i++) {
// 左右端点独立选择，贡献次数是两侧可选数量的乘积。
long leftChoices = i - prevLess[i];
long rightChoices = nextLessEqual[i] - i;
ans = (ans + arr[i] * leftChoices % MOD * rightChoices) % MOD;
}
return (int) ans;
}
}
func sumSubarrayMins(arr []int) int {
const mod int64 = 1_000_000_007
n := len(arr)
prevLess := make([]int, n)
nextLessEqual := make([]int, n)
stack := make([]int, 0, n)
for i := 0; i < n; i++ {
// 左扫弹掉相等值，左界只保留严格更小者。
for len(stack) > 0 && arr[stack[len(stack)-1]] >= arr[i] {
stack = stack[:len(stack)-1]
}
if len(stack) == 0 {
prevLess[i] = -1
} else {
prevLess[i] = stack[len(stack)-1]
}
stack = append(stack, i)
}
stack = stack[:0]
for i := n - 1; i >= 0; i-- {
// 右扫保留相等值，一严一松把重复最小值的区间交给最右者。
for len(stack) > 0 && arr[stack[len(stack)-1]] > arr[i] {
stack = stack[:len(stack)-1]
}
if len(stack) == 0 {
nextLessEqual[i] = n
} else {
nextLessEqual[i] = stack[len(stack)-1]
}
stack = append(stack, i)
}
var ans int64
for i, value := range arr {
// 左右端点独立选择，贡献次数是两侧可选数量的乘积。
leftChoices := int64(i - prevLess[i])
rightChoices := int64(nextLessEqual[i] - i)
ans = (ans + int64(value)*leftChoices%mod*rightChoices) % mod
}
return int(ans)
}
复杂度分析
- 时间复杂度：$O(n)$。每个下标在两轮扫描中都至多入栈、出栈一次。
- 空间复杂度：$O(n)$。两个边界数组和单调栈最多各保存 $n$ 个元素。
关键点总结
[!green]
- 将“枚举子数组”改成“统计每个元素的贡献”，才能把复杂度降到线性。
- 左右端点独立选择，所以贡献次数是两侧选择数的乘积。
- 重复值必须采用一严一松的边界规则；严格方向互换也可以，但必须保持不对称。
- 栈存下标而不是值，因为贡献需要边界距离。
易错点总结
[!yellow]
- 两侧都用严格小于：重复最小值会让同一子数组被重复统计。
- 两侧都用小于等于：重复最小值之间的子数组会被漏掉。
- 第二轮前没有清空栈，会把第一轮残留的下标当成右边界。
- 使用
int计算乘积会溢出；应先提升为long/int64，再取模。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 828. 统计子串中的唯一字符 | 困难 | 同样按每个位置对多少子数组负责来计贡献，本题边界由更小元素决定，原题由相同字符位置决定。 |
| 2104. 子数组范围和 | 中等 | 区间最大值减最小值之和可拆成两次贡献计数，本题是其中的最小值部分。 |
| 84. 柱状图中最大的矩形 | 困难 | 用单调栈确定元素能影响的连续区间边界；本题统计每个值作为区间最小值的贡献，该题以每根柱高计算最大矩形面积。 |
| 85. 最大矩形 | 困难 | 用单调栈确定元素能影响的连续区间边界；本题统计每个值作为区间最小值的贡献，该题逐行累计柱高并复用直方图算法。 |