LeetCode/子数组的最小值之和

给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。

1. 单调栈

假如要遍历所有区间，哪怕可以直接获得最小值，时间复杂度也是O（n²）
这里我们不逐个找对应区间，而是计算每个值对区间的贡献，可以将时间复杂度降到O（n）
其实也就找遍历时当前值的左边界和右边界，在这个区间内该值为最小值，即可直接计算出，该值会对多少个区间做出贡献
先用单调栈找左右两边下一个更小值的坐标即可

class Solution {
public:
    int sumSubarrayMins(vector<int>& arr) {
        int n = arr.size();
        vector<int> monoStack; //单调栈
        vector<int> left(n), right(n);//左右边界
        for (int i = 0; i < n; i++) {//从左往右找左边更小值
            while (!monoStack.empty() && arr[i] <= arr[monoStack.back()]) {//把更大的值挤出来，相等的视为更大，区间计算的时候不影响
                monoStack.pop_back();
            }
            left[i] = i - (monoStack.empty() ? -1 : monoStack.back()); //左区间长度
            monoStack.emplace_back(i);//放入坐标
        }
        monoStack.clear();
        for (int i = n - 1; i >= 0; i--) { //从右往左找右边更小值
            while (!monoStack.empty() && arr[i] < arr[monoStack.back()]) {
                monoStack.pop_back();
            }
            right[i] = (monoStack.empty() ? n : monoStack.back()) - i; //右区间长度
            monoStack.emplace_back(i);
        }
        long long ans = 0;
        long long mod = 1e9 + 7;
        for (int i = 0; i < n; i++) { //计算每个值的贡献
            ans = (ans + (long long)left[i] * right[i] * arr[i]) % mod; 
        }
        return ans;
    }
};