lc907 子数组的最小值之和

给定数组arr[n]，求所有子数组中最小值的和，答案对1e9+7取模。
1<=n<=30000; 1<=arr[i]<=30000

考虑每个数作为最小值对应的子数组有多少个，计算对答案的贡献，而子数组的个数可以用单调栈来维护。数组元素可能相同，为了避免重复计数，用半开半闭区间。

class Solution {
public:
    int sumSubarrayMins(vector<int>& arr) {
        int n = arr.size();
        vector<int> L(n), R(n), s;
        for (int i = 0; i < n; i++) {
            while (!s.empty() && arr[i] < arr[s.back()])
                s.pop_back();
            L[i] = s.empty() ? -1 : s.back();
            s.push_back(i);
        }
        s.clear();
        for (int i = n-1; i >= 0; i--) {
            while (!s.empty() && arr[i] <= arr[s.back()])
                s.pop_back();
            R[i] = s.empty() ? n : s.back();
            s.push_back(i);
        }
        long long ans = 0;
        for (int i = 0; i < n; i++) {
            ans += 1LL * arr[i] * (i-L[i]) * (R[i]-i);
            ans %= 1000000007;
        }
        return ans;
    }
};