题解 | 子数组的最小值之和

class Solution {
public:
    //对于数组中的一个数，看他的左边有多少大于他的数，右边有多少大于它的数，两个值相乘，即以本值为最小值的连续子树组的个数，
    //要找到最近的小于它的数，使用栈，递增栈，保留的是局部最小值，只用比较局部最小值即可；数组记录全局最小值；
    int sumSubarr(vector<int>& nums) {
        const int MOD = 1e9 + 7;
        int n = nums.size();

        stack<int> stk;
        vector<int> left(n);
        vector<int> right(n);

        for(int i=0; i<=n-1; ++i){
            while(!stk.empty() && nums[stk.top()] > nums[i]){ //这里把大于它的数去掉，保留了等于，防止左边扩张重复；
                stk.pop();
            }
            if(stk.empty())left[i] = i+1;
            else left[i] = i - stk.top();

            stk.push(i);
        }

        stk = stack<int>();

        for(int i=n-1; i>=0; --i){
            while(!stk.empty() && nums[stk.top()] >=nums[i]){ //这里把等于它的数也去掉了，因为左边已经限制了相同数的范围，即左边是不交叉覆盖的连续子数组，右边可以交叉覆盖，结果也是不同的子数组；
                stk.pop();
            }
            right[i] = stk.empty()? n-i : stk.top() - i;
            stk.push(i);
        }

        long long res = 0;
        for(int i=0; i<n; ++i){
            res = (res + (long long)nums[i]*left[i]*right[i] ) % MOD;
        }

        return res;
    }
};