【数据结构运用】单调栈 + 乘法原理 运用题
题目描述
这是 LeetCode 上的「907. 子数组的最小值之和」，难度为「中等」。
Tag : 「数学」、「单调栈」
给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。
由于答案可能很大，因此 返回答案模
。
示例 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
提示：
单调栈 + 数学
原问题为求所有子数组的最小值之和，其可等价为求每个
对答案的贡献，即每个
可作为多少个子数组的最小值。
假定我们能预处理出两数组 l 和 r 分别代表
作为子数组最小值时，其所能到达的最远两端：
l[i] = a代表下标
为
能够作为子数组最小值时的最远左边界，即为
左边第一个比其小的元素（若不存在，则为
）
r[i] = b代表跳表
为
能够作为子数组最小值时的最远右边界，即为
右边第一个比其小的元素（若不存在，则为
）
子数组左端点个数为
个，右端点个数为
个，根据乘法原理可知，子数组个数为两者乘积，每个子数组对答案的贡献为
。
由于 arr 可能有重复元素，我们需要考虑取左右端点时，是取成「小于等于」还是「严格小于」：
- 若两端均取成严格小于，且两端中间存在与
等值元素，会导致相同子数组被重复统计；
- 若两端均取成小于等于，且两端恰好存在与
等值元素，会导致原本可以被添加到子数组的等值元素漏加；
- 若一端取成严格小于，另一端取成小于等于，可确保不重不漏。
至于预处理 l 和 r 则可以使用「单调栈」求解，对「单调栈」不了解的同学可以看 关于 RMQ 的若干解法 中的解法四。
代码：
class Solution {
int MOD = (int)1e9+7;
public int sumSubarrayMins(int[] arr) {
int n = arr.length;
int[] l = new int[n], r = new int[n];
Arrays.fill(l, -1); Arrays.fill(r, n);
Deque<Integer> d = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
while (!d.isEmpty() && arr[d.peekLast()] >= arr[i]) r[d.pollLast()] = i;
d.addLast(i);
}
d.clear();
for (int i = n - 1; i >= 0; i--) {
while (!d.isEmpty() && arr[d.peekLast()] > arr[i]) l[d.pollLast()] = i;
d.addLast(i);
}
long ans = 0;
for (int i = 0; i < n; i++) {
int a = l[i], b = r[i];
ans += (i - a) * 1L * (b - i) % MOD * arr[i] % MOD;
ans %= MOD;
}
return (int) ans;
}
}
- 时间复杂度：
- 空间复杂度：
最后
这是我们「刷穿 LeetCode」系列文章的第 No.907 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
腾讯云开发者
