NC386 子数组的最小值之和

思路：

class Solution {
public:
    int sumSubarr(vector<int>& nums) {
        int n=nums.size();
        long ans=0;
        //leftmin用于存每个元素左边第一个小于本身的元素的位置
        //rightmin用于存每个元素右边第一个小于等于本身的元素的位置
        vector<int>leftmin(n,-1);
        vector<int>rightmin(n,n);
        //进行取余10^9+7
        const int M=1000000007;
        //用单调栈维护
        stack<int>stack1;
        //正向遍历找到每个元素左边第一个小于等于本身的元素的位置，
        //但是记录的时候就反着记：记每个元素右边第一个小于等于本身的元素的位置
        for(int i=0;i<n;i++){
            while(!stack1.empty()&&nums[stack1.top()]>nums[i]){
                rightmin[stack1.top()]=i;
                stack1.pop();
            }
            stack1.push(i);
        }
        //调用无参构造函数将栈清空
        stack1=stack<int>();
        //反向遍历找到右边第一个小于本身的元素的位置
        for(int i=n-1;i>=0;i--){
            while(!stack1.empty()&&nums[stack1.top()]>=nums[i]){
                leftmin[stack1.top()]=i;
                stack1.pop();
            }
            stack1.push(i);
        }
        //推导出来的公式：以nums[i]为最小元素的区间个数时left[i]*right[i]
        //所以以nums[i]为最小元素之和是：nums[i]*left[i]*right[i]
        for(int i=0;i<n;i++){
            int l=leftmin[i];
            int r=rightmin[i];
            ans+=(long)((r-i)*(i-l)%M)*nums[i]%M;
        }
        return ans%M;
    }
};