LeetCode 907題解

https://leetcode.com/problems/sum-of-subarray-minimums/description/
連続するサブシーケンスの中で最小値の和を求めます.
各位置ごとに左と右でサブシーケンスを検索し、サブ列の数*A[i]を答え、サブ列の数は左から最も遠い距離*右から最も遠い距離である.
暴力的な検索はタイムアウトし、スタックを使用して前の順序の状況を記録することができ、後の順序の状況も記録することができます.

#define mod 1000000007

class Solution {
public:
    int sumSubarrayMins(vector& A) {
        int n = A.size();
        int res =0;
        stack st;
        for(int i=0;iA[i])
                st.pop();
            int left = st.empty() ? -1:st.top();
            st.push(i);
            int j=i+1;
            while(j=A[i]) j++;

            res = res +  ((i-left)*(j-i) % mod) *A[i] ;
            res = res % mod;
        }
        return res;
    }
};