题目：
给定一个整数数组 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 * 104
1 <= arr[i] <= 3 * 104
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/sum-of-subarray-minimums
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路：
先记录一下我没通过的解题思路：
我想利用双循环来解题，外层循环表示从连续子数组的开始，内层循环表示连续子数组的结束，这样数组中的每个单个元素也能相加，遍历过程中也能更新最小值，以及得到求和，最后将和与10^9 + 7取模即可。
但是用例过不去，我还找不出来原因，哭了我这个小垃圾~
问题代码：
1 class Solution { 2 public int sumSubarrayMins(int[] arr) { 3 int sum = 0, n = arr.length; 4 for(int i = 0; i < n; i++){ 5 sum += arr[i]; 6 int min_num = arr[i]; 7 for(int j = i + 1; j < n; j++){ 8 if(arr[j] > min_num){ 9 sum += min_num; 10 }else{ 11 sum += arr[j]; 12 min_num = Math.min(min_num, arr[j]); 13 } 14 } 15 } 16 int MOD = 1_000_000_007; 17 return (int)(sum % MOD); 18 } 19 }
参考评论区的各位大佬，得到以下题解~
单调栈+贡献法：
①贡献法：
例如:[1,4,2,3,1]中2是子数组[2]、[4,2]、[2,3]、[4,2,3]的最小值，那么2对答案的贡献就是2*4 = 8。
由于以2为连续子数组中的最小值，那么连续子数组中就不能包含比2小的数，因此就可以找到2左右两侧比它小的数的下标，这样就可以确定以2为最小值的连续子数组的边界范围。左右两边比2小的边界范围在(0,4)，闭区间为[1,3]。
设arr[i]对应的边界为开区间(L,R)，子数组需要包含arr[i]，故：
- 左边的下标可以是：L, L+1, L+2，…，i，一共有i-L个；
- 右边的下标可以是：i，i+1，i+2，…，R-1,一共有R-i个；
在arr中不含重复元素的前提下，以arr[i]为最小值的数组个数为 (i-L)*(R-i) ，对答案的贡献值为 arr[i] *(i-L)*(R-i) （类比：上衣有n件，裤子有m条，则一共有 n * m中搭配方法）。注意：如果左侧没有比 arr[i]小的元素，则L= -1，如果右侧没有比 arr[i]小的元素，则R= n，
如果arr中包含重复元素，例如[1,2,4,2,3,1]，第一个2和第二个2对应的边界为(0,5)，都包含了子数组[2,4,2,3]，这样就会计算同一个子数组。
这样需要修改一下边界的定义，将左边界改为小于等于arr[i]的元素下标，右边界依然为小于arr[i]的元素下标，那么：第一个2对应的边界为(0,5)，第二个2对应的边界为(1,5)。
单调栈：参考@【爪哇缪斯L5】：https://leetcode.cn/problems/sum-of-subarray-minimums/solution/-by-muse-77-367z/
构建一个单调递增的栈，里面存放的是元素的下标，如果栈为空，那么直接入栈，如果栈不为空，则进行如下操作：
- 如果 栈顶元素对应的值 >= arr[i]：就弹出栈顶元素，直到栈为空或者栈顶元素对应的值更小，此时栈顶就是最近更小值的位置，即为左边界，即(新的栈顶元素， i)，反过来想想，对于每个出栈的元素，当前元素arr[i]就是向右比它更小的第一个元素，这样也就得到右边界（结合下面的图解进行理解）；
- 如果 栈顶元素对应的值 < arr[i]：则arr[i]直接入栈
例如：
当遍历完整个数组以后，栈中仍然还存在元素，让剩下元素出栈，根据题目中【提示】部分描述，1 <= arr[i] <= 3 * 10^4,所以，arr数组中所有元素都是大于0的，那么我们就虚拟一个元素将其放入堆栈中，因为堆栈中所有元素的值都大于0，所以也就都会被执行出栈操作了。
java代码：
1 class Solution { 2 private static final long MOD = 1000000007; 3 public int sumSubarrayMins(int[] arr) { 4 long ans = 0; 5 Deque<Integer> stack = new ArrayDeque<>(); 6 //最左边界哨兵入栈，-1是索引 7 stack.push(-1); 8 for(int i = 0; i <= arr.length; i++){ 9 //添加末尾哨兵，已经超过数组长度 10 //则设一个虚拟哨兵索引为n对应的值为0，方便剩余元素出栈 11 int m = i < arr.length ? arr[i] : 0; 12 while(stack.size() > 1 && arr[stack.peek()] >= m){ 13 int r = stack.pop(); 14 //当前栈顶的贡献值 15 //(栈顶-弹出后的栈顶)*（当前值的下标-弹出栈顶） 16 ans += (long) arr[r] * (r - stack.peek()) * (i - r); 17 } 18 stack.push(i); 19 } 20 return (int)(ans % MOD); 21 } 22 }
原文地址：http://www.cnblogs.com/liu-myu/p/16834751.html
