Sum of Subarray Minimumse

907. Sum of Subarray Minimumse

class Solution {
public:
    int sumSubarrayMins(vector<int>& arr) {
        int len = arr.size();
        stack<pair<int, int>> sp, sn;
        vector<int> l(len), r(len);
        for (int i = 0; i < len; ++i) l[i] = i + 1;
        for (int i = 0; i < len; ++i) r[i] = len - i;

        for (int i = 0; i < len; ++i) {
            while (!sp.empty() && sp.top().first > arr[i]) sp.pop();
            l[i] = sp.empty() ? i + 1 : i - sp.top().second;
            sp.push({arr[i], i});
        
            while (!sn.empty() && sn.top().first > arr[i]) {
                r[sn.top().second] = i - sn.top().second;
                sn.pop();
            }
            sn.push({arr[i], i});
        }
        
        int result = 0;
        for (int i = 0; i < len; ++i) {
            result = (result + (long long)arr[i] * l[i] * r[i]) % 1000000007;
        }
        return result;
    }
};

각 인덱스의 값이 최소값이 되는 subarray 의 수는 인덱스의 값보다 작은 값 까지의 좌, 우 거리의 곱과 같다.
monotonouse increase stack 으로 좌, 우 거리를 구해놓고 인덱스의 값과 곱한 뒤 모두 더한다.

Time: O(n)

• 주어진 arr 모두 순회 하는데 n

Space: O(n)

• 스택 크기 n + 거리 값 저장해둔 리스트 n