LeetCode 907. 子数组的最小值之和
目录
题目描述
题意分析
给定数组
arr，要把它所有连续子数组各自的最小值加起来，结果对 $10^9 + 7$ 取模。注意求的既不是某一个子数组的最小值，也不是这些最小值里的最大或最小者，而是「每个子数组各贡献一份自己的最小值」这样一个总和。长度为 n 的数组一共有 $n(n+1)/2$ 个非空子数组。约束里 n 最大到 $3 \times 10^4$，子数组数量能到大约 $4.5 \times 10^8$——光是把它们逐个列出来就已经不可接受，所以必须找到线性或接近线性的做法，绝不能按子数组逐个处理。
元素范围是 1 到 $3 \times 10^4$，全是正数，但允许出现重复值。重复值是本题最容易出问题的地方：当一个子数组里有多个位置同时取到最小值时，这个子数组只能被计入一次，因此必须有一套明确规则把它唯一地归给其中某一个位置。
题目要求取模，说明中间量会很大。边界包括：n 为 1、全部元素相等、严格递增、严格递减，以及累加过程中的整型溢出。
解法：单调栈统计元素贡献
核心思路
枚举所有子数组并维护最小值需要 $O(n^2)$。更好的统计口径是：不逐个处理子数组，而是计算每个
arr[i]会成为多少个子数组的最小值。对每个下标
i，寻找两个边界：
prevLess[i]：左侧第一个严格小于arr[i]的位置，不存在时为-1；nextLessEqual[i]：右侧第一个小于等于arr[i]的位置，不存在时为n。左端点有
\[arr[i] \times (i-prevLess[i]) \times (nextLessEqual[i]-i)\]i - prevLess[i]种选择，右端点有nextLessEqual[i] - i种选择，因此arr[i]的贡献为：两侧必须一边严格、一边非严格。本文采用“左侧严格小于、右侧小于等于”，相等最小值出现多次时，子数组统一归给最右侧的那个位置。这样每个子数组恰好被统计一次。
两个边界都可用单调递增栈在线性时间内求出。栈保存下标，每个下标最多入栈、出栈各一次。
解题步骤
- 从左向右扫描。弹出所有值大于等于
arr[i]的下标，栈顶就是左侧第一个严格更小的位置。- 清空栈，从右向左扫描。弹出所有值严格大于
arr[i]的下标，栈顶就是右侧第一个小于等于它的位置。- 对每个
i计算左右端点的选择数，相乘后再乘arr[i]，累加时使用 64 位整数并取模。以
[3,1,2,4]为例，prevLess = [-1,-1,1,2]，nextLessEqual = [1,4,4,4]。四个位置的贡献依次为3、6、4、4，总和为17。
代码实现
import java.util.ArrayDeque;
import java.util.Deque;
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$ 个元素。
关键点总结
- 将“枚举子数组”改成“统计每个元素的贡献”，才能把复杂度降到线性。
- 左右端点独立选择，所以贡献次数是两侧选择数的乘积。
- 重复值必须采用一严一松的边界规则；严格方向互换也可以，但必须保持不对称。
- 栈存下标而不是值，因为贡献需要边界距离。
易错点总结
- 两侧都用严格小于：重复最小值会让同一子数组被重复统计。
- 两侧都用小于等于：重复最小值之间的子数组会被漏掉。
- 第二轮前没有清空栈，会把第一轮残留的下标当成右边界。
- 使用
int计算乘积会溢出；应先提升为long/int64，再取模。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 739. 每日温度 | 中等 | 单调栈入门 |
| 496. 下一个更大元素 I | 简单 | 预处理加映射查询 |
| 503. 下一个更大元素 II | 中等 | 环形数组单调栈 |
| 155. 最小栈 | 中等 | 辅助栈维护最小值 |
| 84. 柱状图中最大的矩形 | 困难 | 左右扩展边界求面积 |
| 85. 最大矩形 | 困难 | 逐行压缩成柱状图 |
| 42. 接雨水 | 困难 | 单调栈按层积水 |