单调栈｜907.子数组的最小值之和

题目链接
求蓝色柱体对答案的贡献
蓝色柱体对答案的贡献对答案的贡献为$AB\times BF+AE\times EF?AB\times EF=AB\times CD+AE\times EF$
于是在单调栈的实现过程中，应该实现能向左找到严格比自己小，向右找到比自己小或者等于的数字的效果。

class Solution {
public:
    int sumSubarrayMins(vector<int>& arr) {
        long long  ans = 0;
        stack<int > st;
        long long  rmin[arr.size()],lmin[arr.size()];
        for(int i=0;i<arr.size();i++)
            rmin[i] = arr.size(),lmin[i] = -1;
        for(int i=0;i<arr.size();i++){
            if(st.empty()||arr[st.top()]<=arr[i]){
                st.push(i);
                continue;
            }
            else{
                while(st.size()&&arr[st.top()]>arr[i]){
                    rmin[st.top()] = i;
                    st.pop();
                }
                st.push(i);
            }
        }
        while(st.size()) st.pop();
        for(int i=arr.size()-1;i>=0;i--){
            if(st.empty()||arr[st.top()]<arr[i]){
                st.push(i);
                continue;
            }
            else{
                while(st.size()&&arr[st.top()]>=arr[i]){
                    lmin[st.top()] = i;
                    st.pop();
                }
                st.push(i);
            }
        }
        for(int i=0;i<arr.size();i++)
            ans = (ans+arr[i]*(i-lmin[i])*(rmin[i]-i)%(int(1E9+7)))%(int(1E9+7));
        return ans;
    }
};

晓源算法专栏