难度中等

给定一个整数数组 arr ，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。

由于答案可能很大，因此 返回答案模 10^9 + 7 。

示例 1：

输入：arr = [3,1,2,4]

输出：17

解释：

子数组为 [3]，[1]，[2]，[4]，[3,1]，[1,2]，[2,4]，[3,1,2]，[1,2,4]，[3,1,2,4]。

最小值为 3，1，2，4，1，1，2，1，1，1，和为 17。

示例 2：

输入：arr = [11,81,94,43,3]

输出：444

提示：

1 <= arr.length <= 3 * 10^4
1 <= arr[i] <= 3 * 10^4

# 暴力

	class Solution {
	int MOD = 1000000007;

	public int sumSubarrayMins(int[] arr) {
	// 3 2 1 4
	int ans = 0;
	int n = arr.length;
	for (int i = 0; i < n; i++) {
	int mn = Integer.MAX_VALUE;
	for (int j = i; j >= 0; j--) {
	mn = Math.min(mn, arr[j]);
	ans = (ans + mn) % MOD;
	}
	}
	return ans;
	}
	}

# 贡献法 + 单调栈 + 动态规划

设 $dp[i]$ 为以 $i$ 结尾的子数组最小值之和

若当前下标为 $i$ ，寻找 $i$ 左边第一个比 $num[i]$ 小的下标 $j$ 。

此时区间 $[j + 1 \sim i]$ 中元素都 $>nums[j]$

贡献值： $dp[i] = dp[j] + [i - (j + 1) + 1] * nums[i]$

$dp[j]$ ：以 $j$ 结尾的子数组最小值之和

由于 $[j + 1 \sim i]$ 中元素都 $>nums[j]$ ，所以右边为 $[i - (j + 1) + 1] * nums[i]$

最后只要对各个贡献值 $dp[i]$ 求和就是了

	class Solution {
	int MOD = 1000000007;

	public int sumSubarrayMins(int[] arr) {
	// 3 2 1 4
	long ans = 0;
	int n = arr.length;
	// 上一个比 nums [i] 小的元素下标 j
	// 此时 [j + 1 ~ i] 元素必然都比 nums [i] 大
	// 贡献值 dp [i] = dp [j] + [i - (j + 1) + 1] * nums [i]
	// j 结尾的子数组最小值之和 + 中间的元素个数 * 当前元素

	// [单调递增的下标]
	Deque<Integer> st = new LinkedList<>();
	long[] dp = new long[n];
	for (int i = 0; i < n; i++) {
	// 不断弹出栈顶元素 peek 直至 peek <= num
	while (!st.isEmpty() && arr[st.peekFirst()] > arr[i]) {
	st.pollFirst();
	}
	// 左边没有比它小的元素
	dp[i] = (long) (i + 1) * arr[i];
	if (!st.isEmpty()) {
	int j = st.peekFirst();
	dp[i] = (dp[j] + ((long) (i - (j + 1) + 1) * arr[i]) % MOD) % MOD;
	}
	st.offerFirst(i);
	ans = (ans + dp[i]) % MOD;
	}
	return (int) ans;
	}
	}

# 贡献法 + 单调栈

对每个数，算出它是哪些子数组的最小值。

当前下标 $i$ ，往左边寻找第一个小于 $nums[i]$ 的元素下标 $l$ ，往右边寻找第一个小于等于 $nums[i]$ 的元素下标 $r$

为什么需要小于等于 $nums[i]$ 呢？

例如： $[71,55,82,55]$

若小于 $i$

$i = 1$ 时候的其中一个子数组： $[55,82,55],[71,55,82,55]$

$i = 3$ 时候的其中一个子数组： $[55,82,55],[71,55,82,55]$

重复，则结果会变大。

若小于等于 $i$

$i = 1$ 时候的其中一个子数组： $[55,82],[71,55,82]$

$i = 3$ 时候的其中一个子数组： $[82,55]$

则不会出现重复的子数组

此时：开区间 $(l,r)$ 所包含所有子数组最小值就为 $nums[i]$

子数组的左端点可以是： $l + 1,l+2,...,i$ ，共有 $i-l$ 个
子数组的右端点可以是： $i,i+2,...,r$ ，共有 $r-i$ 个
由乘法原理：对答案的贡献为 $nums[i] \cdot(i - l)\cdot (r-i)$

可以采用单调栈计算往左（右）寻找第一个小于（小于等于） $nums[i]$ 的元素下标 $l$

# 三次遍历

	class Solution {
	int MOD = 1000000007;

	public int sumSubarrayMins(int[] arr) {
	// 3 2 1 4
	int n = arr.length;
	//l [i]: 下标 i 左边第一个小于 i 的下标，不存在为 -1
	int[] l = new int[n];
	Deque<Integer> lst = new LinkedList<>();
	lst.addFirst(-1);
	for (int i = 0; i < n; i++) {
	while (lst.size() > 1 && arr[lst.peekFirst()] >= arr[i]) {
	lst.pollFirst();
	}
	l[i] = lst.peekFirst();
	lst.addFirst(i);
	}
	//r [i]: 下标 i 右边第一个小于等于 i 的下标，不存在为 n
	int[] r = new int[n];
	Deque<Integer> rst = new LinkedList<>();
	rst.addFirst(n);
	for (int i = n - 1; i >= 0; i--) {
	while (rst.size() > 1 && arr[rst.peekFirst()] > arr[i]) {
	rst.pollFirst();
	}
	r[i] = rst.peekFirst();
	rst.addFirst(i);
	}
	long ans = 0;
	for (int i = 0; i < n; i++) {
	ans = (ans + (long) (i - l[i]) * (r[i] - i) * arr[i]) % MOD;
	}
	return (int) ans;
	}
	}

# 两次遍历

我们可以在计算 $l[i]$ 的同时计算 $r[i]$ ，若栈顶元素 $peek$ 大于等于 $nums[i]$ ，则说明 $peek$ 的右边第一个小于等于 $peek$ 的元素即为 $nums[i]$

	class Solution {
	int MOD = 1000000007;

	public int sumSubarrayMins(int[] arr) {
	// 3 2 1 4
	int n = arr.length;
	//l [i]: 下标 i 左边第一个小于 i 的下标，不存在为 -1
	int[] l = new int[n];
	//r [i]: 下标 i 右边第一个小于等于 i 的下标，不存在为 n
	int[] r = new int[n];

	// 存放的是递增的元素
	Deque<Integer> st = new LinkedList<>();
	st.addFirst(-1);
	for (int i = 0; i < n; i++) {
	while (st.size() > 1 && arr[st.peekFirst()] >= arr[i]) {
	// 此时弹出的栈顶元素 peek 右边第一个小于等于 peek 的元素为 i
	r[st.pollFirst()] = i;
	}
	l[i] = st.peekFirst();
	st.addFirst(i);
	}
	// 说明还有剩余元素
	while (st.size() > 1) {
	r[st.pollFirst()] = n;
	}
	long ans = 0;
	for (int i = 0; i < n; i++) {
	ans = (ans + (long) (i - l[i]) * (r[i] - i) * arr[i]) % MOD;
	}
	return (int) ans;
	}
	}

# 一次遍历

由上述栈中元素可以发现，此时栈顶弹出的 $poll$ 下面的元素正好是 $poll$ 的左边界

因为栈中元素是单调递增的。

例如： $st: [5, 6, 7]$

此时栈顶元素 $7$ 下面元素 $6$ 正好是 $7$ 的左边界

	class Solution {
	int MOD = 1000000007;

	public int sumSubarrayMins(int[] arr) {
	// 3 2 1 4
	int n = arr.length;
	// 存放的是递增的元素
	Deque<Integer> st = new LinkedList<>();
	st.addFirst(-1);
	long ans = 0;
	for (int i = 0; i < n; i++) {
	while (st.size() > 1 && arr[st.peekFirst()] >= arr[i]) {
	// 此时弹出的栈顶元素 poll 右边第一个小于等于 poll 的元素为 i
	Integer v = st.pollFirst();
	// 此时栈顶弹出的 poll 下面的元素正好是 poll 的左边界
	int l = st.peekFirst();
	ans = (ans + (long) (v - l) * (i - v) * arr[v]) % MOD;
	}
	st.addFirst(i);
	}
	// 说明还有剩余元素，此时内部都是递增的，其右边界为 n
	while (st.size() > 1) {
	// 此时弹出的栈顶元素 poll 右边第一个小于等于 poll 的元素为 i
	Integer v = st.pollFirst();
	// 此时栈顶弹出的 poll 下面的元素正好是 poll 的左边界
	int l = st.peekFirst();
	ans = (ans + (long) (v - l) * (n - v) * arr[v]) % MOD;
	}

	return (int) ans;
	}
	}

可以合并在一起

	class Solution {
	int MOD = 1000000007;

	public int sumSubarrayMins(int[] arr) {
	// 3 2 1 4
	int n = arr.length;
	// 存放的是递增的元素
	Deque<Integer> st = new LinkedList<>();
	st.addFirst(-1);
	long ans = 0;
	for (int r = 0; r <= n; r++) {
	// 说明还有剩余元素，此时内部都是递增的，其右边界为 n，需要都满足条件
	int x = r == n ? -1 : arr[r];
	while (st.size() > 1 && arr[st.peekFirst()] >= x) {
	// 此时弹出的栈顶元素 poll 右边第一个小于等于 poll 的元素为 r
	Integer i = st.pollFirst();
	// 此时栈顶弹出的 poll 下面的元素正好是 poll 的左边界
	int l = st.peekFirst();
	ans = (ans + (long) (i - l) * (r - i) * arr[i]) % MOD;
	}
	st.addFirst(r);
	}
	return (int) ans;
	}
	}

贡献法单调栈

栈单调栈中等贡献法