LeetCode 907. 子数组的最小值之和（单调栈）

示例：
输入：[3,1,2,4]
输出：17
解释：
子数组为 [3]，[1]，[2]，[4]，[3,1]，[1,2]，[2,4]，[3,1,2]，[1,2,4]，[3,1,2,4]。 
最小值为 3，1，2，4，1，1，2，1，1，1，和为 17。
 
提示：
1 <= A <= 30000
1 <= A[i] <= 30000

class Solution {
public:
    int sumSubarrayMins(vector<int>& A) {
        int n = A.size();
        vector<int> L(n, -1), R(n, -1);
        stack<int> s;
        for(int i = 0 ; i < n; ++i)
        {
            while(!s.empty() && A[s.top()] > A[i])
                s.pop();
            L[i] = (s.empty() ? 0 : s.top()+1);
            s.push(i);
        }
        while(!s.empty()) s.pop();
        for(int i = n-1 ; i >= 0; --i)
        {
            while(!s.empty() && A[s.top()] >= A[i])
            //两次等号只能取一次 [71,55,82,55]，否则答案有重复
                s.pop();
            R[i] = (s.empty() ? n-1 : s.top()-1);
            s.push(i);
        }
        int ans = 0, mod = 1e9+7;
        for(int i = 0; i < n; ++i)
        {
            // cout << L[i] << " " << R[i] << endl;
            ans = (ans + 1LL*(i-L[i]+1)*(R[i]-i+1)*A[i]%mod)%mod;
        }
        return ans;
    }
};