AM 1734. Sum of Subarray Minimums

Code(Language:C++) (Judger:cloudjudge-cluster-7)

class Solution {
public:
    /**
     * @param A: an array
     * @return: the sum of subarray minimums
     */
    int sumSubarrayMins(vector<int> &A) {
        // Write your code here.
        // 单调栈 找 左右两边 第一个比当前值 小的值。
        //右边第一个小的：单调递减栈
        //左边第一个小的: 单调递增栈。
        //这个题和 max area in histgram 和 in matrix基本思路一样的。
        //值得注意
        const int size = A.size(); 
        long mod = 1000000007;
        if(size == 0){
            return 0; 
        }
        stack<int> stk1; 
       // vector<int> right(size, 0);
        A.push_back(0); 
        int res = 0; 
        for(int i = 0; i <= size; i++){
            while(!stk1.empty() && A[stk1.top()] >= A[i]){ // inceasing?  
                int tmp = stk1.top();
                stk1.pop(); 
                //right[tmp] = i;
                int left = stk1.empty() ? -1 : stk1.top();
                res = (res + A[tmp] * (i - tmp) * (tmp - left)) % mod; 
            }
            stk1.push(i); 
        }
        return res; 
    }
};