907. 子数组的最小值之和
题目描述
输入整数数组 arr。
考虑 arr 的每一个非空连续子数组，取出它的最小值，再把所有这些最小值加起来。
结果可能很大，返回总和对 10^9 + 7 取模后的值。
示例 1
输入：arr = [3,1,2,4] 输出：17
解释：10 个子数组的最小值依次为 3、1、2、4、1、1、2、1、1、1，和为 17。
示例 2
输入：arr = [11,81,94,43,3] 输出：444
数据范围
1 <= arr.length <= 3 * 10^41 <= arr[i] <= 3 * 10^4
解题思路：单调栈 + 动态规划（以 i 结尾的子数组最小值之和）
设 dp[i] 为所有以 i 结尾的子数组的最小值之和。找到 i 左边第一个比 arr[i] 小的位置 j：起点在 j+1..i 的 i-j 个子数组最小值都是 arr[i]；起点在 j 及更左的子数组，最小值和以 j 结尾的对应子数组一样，和为 dp[j]。所以 dp[i] = dp[j] + (i - j) · arr[i]。“左边第一个更小的数”用单调递增栈求。答案为 Σ dp[i]。
为什么正确
处理完 i 后，栈中下标对应的值严格递增，栈顶是 i；弹掉的下标都不可能再成为后面位置的“左边第一个更小数”。
复杂度分析
时间 O(n)（每个下标最多入栈、出栈各一次），空间 O(n)。
易错点
出栈条件用 >=（相等也弹出），让 j 是“严格更小”的位置。相等元素此时会被当前的 arr[i] 统一计入，不重不漏。C++/Java 的 (i-j)·arr[i] 要用 long，并及时取模。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def sumSubarrayMins(self, arr: List[int]) -> int:
MOD = 10 ** 9 + 7
n = len(arr)
dp = [0] * n
stack = []
ans = 0
for i in range(n):
while stack and arr[stack[-1]] >= arr[i]:
stack.pop()
j = stack[-1] if stack else -1
dp[i] = (dp[j] if j >= 0 else 0) + (i - j) * arr[i]
stack.append(i)
ans += dp[i]
return ans % MODclass Solution {
public int sumSubarrayMins(int[] arr) {
final long MOD = 1_000_000_007L;
int n = arr.length;
long[] dp = new long[n];
int[] stack = new int[n]; int top = 0;
long ans = 0;
for (int i = 0; i < n; i++) {
while (top > 0 && arr[stack[top - 1]] >= arr[i]) {
top--;
}
int j = top > 0 ? stack[top - 1] : -1;
dp[i] = ((j >= 0 ? dp[j] : 0) + (long) (i - j) * arr[i]) % MOD;
stack[top++] = i;
ans = (ans + dp[i]) % MOD;
}
return (int) (ans % MOD);
}
}class Solution {
public:
int sumSubarrayMins(vector<int>& arr) {
const long long MOD = 1e9 + 7;
int n = arr.size();
vector<long long> dp(n, 0);
vector<int> stack;
long long ans = 0;
for (int i = 0; i < n; i++) {
while (!stack.empty() && arr[stack.back()] >= arr[i]) {
stack.pop_back();
}
int j = stack.empty() ? -1 : stack.back();
dp[i] = ((j >= 0 ? dp[j] : 0) + (long long)(i - j) * arr[i]) % MOD;
stack.push_back(i);
ans = (ans + dp[i]) % MOD;
}
return ans % MOD;
}
};func sumSubarrayMins(arr []int) int {
const MOD = 1_000_000_007
n := len(arr)
dp := make([]int, n)
stack := []int{}
ans := 0
for i := 0; i < n; i++ {
for len(stack) > 0 && arr[stack[len(stack)-1]] >= arr[i] {
stack = stack[:len(stack)-1]
}
j := -1
if len(stack) > 0 { j = stack[len(stack)-1] }
prev := 0
if j >= 0 { prev = dp[j] }
dp[i] = (prev + (i-j)*arr[i]) % MOD
stack = append(stack, i)
ans = (ans + dp[i]) % MOD
}
return ans % MOD
}var sumSubarrayMins = function(arr) {
const MOD = 1000000007;
const n = arr.length;
const dp = new Array(n).fill(0);
const stack = [];
let ans = 0;
for (let i = 0; i < n; i++) {
while (stack.length && arr[stack[stack.length - 1]] >= arr[i]) {
stack.pop();
}
const j = stack.length ? stack[stack.length - 1] : -1;
dp[i] = ((j >= 0 ? dp[j] : 0) + (i - j) * arr[i]) % MOD;
stack.push(i);
ans = (ans + dp[i]) % MOD;
}
return ans % MOD;
};function sumSubarrayMins(arr: number[]): number {
const MOD = 1000000007;
const n = arr.length;
const dp = new Array(n).fill(0);
const stack: number[] = [];
let ans = 0;
for (let i = 0; i < n; i++) {
while (stack.length && arr[stack[stack.length - 1]] >= arr[i]) {
stack.pop();
}
const j = stack.length ? stack[stack.length - 1] : -1;
dp[i] = ((j >= 0 ? dp[j] : 0) + (i - j) * arr[i]) % MOD;
stack.push(i);
ans = (ans + dp[i]) % MOD;
}
return ans % MOD;
}其他解法
主解法按右端点做 DP，一遍单调栈即可；贡献法按最小值元素分组计数，需要左右边界，但思路可以直接套用到更多题目。
解法 2：贡献法（单调栈求左右边界） 时间 O(n)，空间 O(n)
换个角度：对每个 arr[i]，统计它是多少个子数组的最小值。用单调栈求出左边第一个严格更小的位置 L 和右边第一个小于等于它的位置 R，左端点有 i - L 种选法、右端点有 R - i 种选法，贡献就是 arr[i] × (i - L) × (R - i)。一边严格、一边不严格，是为了让有重复最小值的子数组只算一次。
“枚举每个元素做最小值的范围”是一类题的通用套路（如子数组范围和、柱状图中最大的矩形），迁移性强。但重复元素的边界一侧取严格、一侧取非严格，写错就会重复计数或漏计；还要两个边界数组。
class Solution:
def sumSubarrayMins(self, arr: List[int]) -> int:
MOD = 10 ** 9 + 7
n = len(arr)
left = [-1] * n
right = [n] * n
stack = []
for i in range(n):
while stack and arr[stack[-1]] >= arr[i]:
right[stack.pop()] = i
left[i] = stack[-1] if stack else -1
stack.append(i)
ans = 0
for i in range(n):
ans += arr[i] * (i - left[i]) * (right[i] - i)
return ans % MODclass Solution {
public int sumSubarrayMins(int[] arr) {
final long MOD = 1_000_000_007;
int n = arr.length;
int[] left = new int[n], right = new int[n];
Arrays.fill(right, n);
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) right[stack.pop()] = i;
left[i] = stack.isEmpty() ? -1 : stack.peek();
stack.push(i);
}
long ans = 0;
for (int i = 0; i < n; i++) {
ans = (ans + (long) arr[i] * (i - left[i]) % MOD * (right[i] - i)) % MOD;
}
return (int) ans;
}
}class Solution {
public:
int sumSubarrayMins(vector<int>& arr) {
const long long MOD = 1000000007;
int n = arr.size();
vector<int> left(n, -1), right(n, n), stk;
for (int i = 0; i < n; i++) {
while (!stk.empty() && arr[stk.back()] >= arr[i]) {
right[stk.back()] = i;
stk.pop_back();
}
left[i] = stk.empty() ? -1 : stk.back();
stk.push_back(i);
}
long long ans = 0;
for (int i = 0; i < n; i++) {
ans = (ans + (long long)arr[i] * (i - left[i]) % MOD * (right[i] - i)) % MOD;
}
return ans;
}
};func sumSubarrayMins(arr []int) int {
const MOD = 1_000_000_007
n := len(arr)
left := make([]int, n)
right := make([]int, n)
stack := []int{}
for i := 0; i < n; i++ {
right[i] = n
for len(stack) > 0 && arr[stack[len(stack)-1]] >= arr[i] {
right[stack[len(stack)-1]] = i
stack = stack[:len(stack)-1]
}
left[i] = -1
if len(stack) > 0 {
left[i] = stack[len(stack)-1]
}
stack = append(stack, i)
}
ans := 0
for i := 0; i < n; i++ {
ans = (ans + arr[i]*(i-left[i])%MOD*(right[i]-i)) % MOD
}
return ans
}var sumSubarrayMins = function(arr) {
const MOD = 1000000007;
const n = arr.length;
const left = new Array(n).fill(-1), right = new Array(n).fill(n);
const stack = [];
for (let i = 0; i < n; i++) {
while (stack.length > 0 && arr[stack[stack.length - 1]] >= arr[i]) right[stack.pop()] = i;
left[i] = stack.length > 0 ? stack[stack.length - 1] : -1;
stack.push(i);
}
let ans = 0;
for (let i = 0; i < n; i++) {
ans = (ans + arr[i] * (i - left[i]) % MOD * (right[i] - i)) % MOD;
}
return ans;
};function sumSubarrayMins(arr: number[]): number {
const MOD = 1000000007;
const n = arr.length;
const left = new Array(n).fill(-1), right = new Array(n).fill(n);
const stack: number[] = [];
for (let i = 0; i < n; i++) {
while (stack.length > 0 && arr[stack[stack.length - 1]] >= arr[i]) right[stack.pop()!] = i;
left[i] = stack.length > 0 ? stack[stack.length - 1] : -1;
stack.push(i);
}
let ans = 0;
for (let i = 0; i < n; i++) {
ans = (ans + arr[i] * (i - left[i]) % MOD * (right[i] - i)) % MOD;
}
return ans;
}