力扣907. 子数组的最小值之和（单调栈）

给定一个整数数组 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

利用单调栈来找最小贡献值的边界，该题可参考题解。

 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 };