907. Sum of Subarray Minimums

思路：A[i]是最低值的次数 = （左边连续的大于A[i]的个数+1）*（右边连续大于等于A[i]的个数+1）

class Solution {
public:
    int sumSubarrayMins(vector<int>& A) {
        long long sum = 0;
        int n = A.size();
        vector<int> l(n,-1),r(n,n),st;
        for(int i = 0;i<n;i++){
            while(!st.empty()&&A[st.back()]>A[i])st.pop_back();
            l[i] = st.empty()?-1:st.back();
            st.push_back(i);
        }
        st.clear();
        for(int i = n-1;i>-1;i--){
            while(!st.empty()&&A[st.back()]>=A[i])st.pop_back();//注意这里
            r[i] = st.empty()?n:st.back();
            st.push_back(i);
        }
        for(int i =0;i<n;i++)
        {
            sum += (long long)A[i] *(long long)(i-l[i])*(long long)(r[i]-i);
        }
        return sum%((long long)1e9+7);
    }
};