LeetCode 907.子数组的最小值之和

LeetCode 907.子数组的最小值之和

本题由于每一项都需要遍历到，所以我们要计算所有可能的排列组合情况，所以这道题我们应该从每个元素分别出发，构建单调栈，找到每个元素左边和右边第一个比他小的元素，在这个区间范围内，我们可以断定任何一个子区间得到的最小值都是当前选定这个元素，所以最终的结果就可以很快的由单调栈记录内容的区间长度乘以当前这个元素值就可以得到当前子区间内的所有子数组相加之和，最终将这些结果分别相加即可得到答案

class Solution {
    typedef long long ll;
public:
    int sumSubarrayMins(vector<int>& arr) {
        int n = arr.size();
        vector<int> l(n), r(n);
        stack<int> s;
        for(int i=0;i<n;i++)
        {
            while(!s.empty() && arr[s.top()] > arr[i]) s.pop();
            if(s.empty())   l[i] = -1;
            else l[i] = s.top();
            s.push(i);
        }
        s = stack<int>();
        for(int i=n-1;i>=0;i--)
        {
            while(!s.empty() && arr[s.top()] >= arr[i])  s.pop();
            if(s.empty())   r[i] = n;
            else r[i] = s.top();
            s.push(i);
        }
        int ans=0;
        int MOD = 1e9+7;
        for(int i=0;i<n;i++)
        {
            ans = (ans + (ll)arr[i] * (i - l[i]) * (r[i] - i)) % MOD;
        }
        return ans;
    }
};