Description

Submission

class Solution {
public:
    int sumSubarrayMins(vector<int>& arr) {
        const int M = 1e9 + 7;
        int n = arr.size();

        vector<int> leftSmaller(n); // index of left smaller or equal

        stack<int> stk;

        for(int i = 0; i < n; ++i) {
            while(!stk.empty() && arr[stk.top()] >= arr[i]) stk.pop();
            
            leftSmaller[i] = stk.empty() ? 0 : stk.top() + 1;

            stk.push(i);
        }
        
        long long ret = 0;
        while(!stk.empty()) stk.pop();
        for(int i = n - 1; i >= 0; --i) {
            while(!stk.empty() && arr[stk.top()] > arr[i]) stk.pop();
                
            long long rightSmaller = stk.empty() ? n - 1 : stk.top() - 1;

            ret = (ret + ((rightSmaller - i + 1) *  (i - leftSmaller[i] + 1) * arr[i])) % M;

            stk.push(i);
        }

        return ret;
    }
};


// 3 1 (2 [4] 5 6 1) 2 3

// find next smaller element, but it should be excluded(for convenience)

// increasing monostack