问题：
给定数组，求所有连续子数组的最小值之和。
若所得之数太大，求其mod(10^9 + 7)
Example 1: Input: [3,1,2,4] Output: 17 Explanation: Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1. Sum is 17. Note: 1 <= A.length <= 30000 1 <= A[i] <= 30000
解法：
对于数组中的每一个值A[i]
当它为最小值时，
有：向左连续包含它，且所有元素>=它，的元素个数left[i]；
有：向右连续包含它，且所有元素>=它，的元素个数right[i]；
那么当它为最小值的，连续子数组的个数=left[i]*right[i] （因为要包含它，且为连续的子数组）
那么最小值之和为：A[i]*left[i]*right[i]
同理遍历所有元素，则可得整个数组的最小值之和
1 for(int i=0; i<A.size(); i++){
2 res=(res+ (A[i]*left[i]*right[i]))%mod;
3 }
4 return res;
接下来，需要构建left[i]和right[i]
我们使用递增stack来求得。
left[i] ：A[i]以左，所有元素>=A[i]
right[i]：A[i]以右，所有元素>=A[i]
递增stack：（最终形态）栈内元素：为从原数组最小值起递增，
我们可以同时记录：从上一个栈内元素 stack[i-1] 到该元素 stack[i] 为止，数组内元素的个数，
这些数num一定大于stack[i]，即：num>=stack[i]>stack[i-1]
那么，A[i]的left[i]或者right[i]则=stack[i]+...stack[i-x] (stack[i-x]>=A[i])的累加即可。
下面代码的 increasingL 代表 stack：
1 for(int i=0; i<A.size(); i++){
2 int cout=1;
3 while(!increasingL.empty() && increasingL.top().first>A[i]){
4 cout+=increasingL.top().second;
5 increasingL.pop();
6 }
7 left[i]=cout;
8 increasingL.push({A[i],cout});
9 }
left从左向右存储：左边所有大于A[i]的元素个数
right从右向左存储：右边所有大于A[i]的元素个数
方法一样，只是有一个需要注意的点：
⚠️注意：对于数组中存在重复的数字时，如何处理：
stack的pop时机：一个>= 另一个>
这样，会使得，left的包含两个相同的数值，right不包含两个相同的数值。
对于相同的A[i]，A[j]，一边包含相同数值，一边不包含，相比两边都包含，
会减去一次重复计算的两个数都包含的情况。详细请参考下面的“1”
代码参考：
1 class Solution {
2 public:
3 int sumSubarrayMins(vector<int>& A) {
4 int res=0, mod = (int)1e9 + 7;
5 vector<int> left(A.size());
6 vector<int> right(A.size());
7 stack<pair<int,int>> increasingL,increasingR;
8 //(num,从最小的数开始,stack上一个num为止>本值(比自己大)的个数cout)
9 //e.g.[3,2,1,2,1,4,5,2,3,6]
10 // ^ ^ ^ ^ ^
11 // cout: 3 2 3 1 1
12 // cout([start~1]:>1+自己)=3:[3,2,1]
13 // cout((1~1] :>1+自己)=2:[2,1]
14 // cout((1~2] :>2+自己)=3:[4,5,2]
15 // cout((2~3] :>3+自己)=1:[3]
16 // cout((3~6] :>6+自己)=1:[6]
17 //stack:[{1,cout:3},{1,cout:2},{2,cout:3},{3,cout:1},{6,cout:1}]
18 for(int i=0; i<A.size(); i++){
19 int cout=1;
20 while(!increasingL.empty() && increasingL.top().first>A[i]){
21 //stack:[{1,cout:3},{1,cout:2},{2,cout:3},{3,cout:1},{6,cout:1}]
22 //==的话，就不pop，那么会存储两个1
23 cout+=increasingL.top().second;
24 increasingL.pop();
25 }
26 left[i]=cout;
27 increasingL.push({A[i],cout});
28 }
29 for(int i=A.size()-1; i>=0; i--){
30 int cout=1;
31 while(!increasingR.empty() && increasingR.top().first>=A[i]){
32 //e.g. [3,2,1,2,1,4,5,2,3,6]
33 // ^ ^ ^
34 // cout: 1 1 8
35 //cout([end~1]:>=1)=8:[1,2,1,4,5,2,3,6]
36 //cout((1~2] :>=2)=1:[2]
37 //cout((2~3] :>=3)=1:[3]
38 //stack:[{1,cout:8},{2,cout:1},{3,cout:1}]
39 //==的话，pop，那么会存储一个1
40 //left[第一个1]=3[3,2,1],right[第一个1]=8[1,2,1,4,5,2,3,6]
41 //包含了另一个1->所得子数组包含另一个1
42 //left[第二个1]=2[2,1],right[第二个1]=6[1,4,5,2,3,6]
43 //不包含另一个1->所得子数组不包含另一个1
44 cout+=increasingR.top().second;
45 increasingR.pop();
46 }
47 right[i]=cout;
48 increasingR.push({A[i],cout});
49 }
50 for(int i=0; i<A.size(); i++){
51 res=(res+ (A[i]*left[i]*right[i]))%mod;
52 }
53 return res;
54 }
55 };