给定一个整数数组 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 * 1041 <= arr[i] <= 3 * 104
利用单调栈来找最小贡献值的边界，该题可参考题解。
1 class Solution { 2 public: 3 4 int sumSubarrayMins(vector<int>& arr) { 5 long sum = 0; 6 long mod = 1e9 + 7; 7 long left[arr.size()],right[arr.size()]; 8 stack<long> s; 9 for (long i = 0; i < arr.size(); ++i){ 10 while (!s.empty() && arr[s.top()] > arr[i]){ 11 s.pop(); 12 } 13 if (s.empty()){ //在0~i中arr[i]是最小的 14 left[i] = -1; 15 }else{ //选取i左边第一个比他小的作为左边界 16 left[i] = s.top(); 17 } 18 s.push(i); 19 } 20 while(!s.empty()){ 21 s.pop(); 22 } 23 for (long i = arr.size() - 1;i >= 0; --i){ 24 while(!s.empty() && arr[s.top()] >= arr[i]){ 25 s.pop(); 26 } 27 if (s.empty()){ 28 right[i] = arr.size(); 29 }else{ 30 right[i] = s.top(); 31 } 32 s.push(i); 33 } 34 for (long i = 0;i < arr.size(); ++i){ 35 sum += arr[i] * (i - left[i]) * (right[i] - i) % mod; 36 } 37 return sum % mod; 38 } 39 };