C 解法, 执行用时: 22ms, 内存消耗: 2600KB, 提交时间: 2022-07-18

int sumSubarr(int* nums, int numsLen ) {
    long long z = 0;
    int s[numsLen], t = 0;
    long long v, L, R, a, f;

    for (int i = 0; i < numsLen; i++) {
        v = nums[i];
        while (t > 0 && v < nums[s[t - 1]]) {
            f = s[t - 1];
            a = nums[s[t - 1]];
            if (t - 1 > 0) {
                L = s[t - 2] + 1;
            } else {
                L = 0;
            }
            R = i - 1;

            z = (z + (R - f + 1) * (f - L + 1) * a) % 1000000007;

            t--;
        }
        s[t++] = i;
    }

    while (t > 0) {
        f = s[t - 1];
        a = nums[s[t - 1]];
        if (t - 1 > 0) {
            L = s[t - 2] + 1;
        } else {
            L = 0;
        }
        R = numsLen - 1;
        z = (z + (((R - f + 1) * (f - L + 1) % 1000000007) * a) % 1000000007) %
            1000000007;
        t--;
    }
    return z;
}

C++ 解法, 执行用时: 22ms, 内存消耗: 2976KB, 提交时间: 2022-07-18

class Solution {
  public:
    int sumSubarr(vector<int>& nums) {
        int z = 0;
        int h = nums.size();
        const int a = 1e9 + 7;
        stack<int> s;

        for (int i = 0; i <= h; ++i) {
            int c = (i == h) ? 0 : nums[i];
            while (!s.empty() && c < nums[s.top()]) {
                int f = s.top();
                s.pop();
                int L = f - (s.empty() ? -1 : s.top());
                int R = i - f;
                z = (z + static_cast<long>(nums[f]) * L * R) % a;
            }
            s.push(i);
        }

        return z;
    }
};

C++ 解法, 执行用时: 22ms, 内存消耗: 2980KB, 提交时间: 2022-06-29

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int sumSubarr(vector<int>& nums) {
        // write code here
        int res = 0;
        int n = nums.size();
        const int M = 1e9 + 7;
        stack<int> stk;
        
        for (int i = 0; i <= n; ++i) {
            int cur = (i == n) ? 0 : nums[i];
            while (!stk.empty() && cur < nums[stk.top()]) {
                int idx = stk.top();
                stk.pop();
                
                int left = idx - (stk.empty() ? -1 : stk.top());
                int right = i - idx;
                res = (res + static_cast<long>(nums[idx]) * left * right) % M;
            }
            
            stk.push(i);
        }
        
        return res;
    }
};

C++ 解法, 执行用时: 22ms, 内存消耗: 3032KB, 提交时间: 2022-08-06

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int sumSubarr(vector<int>& nums) {
        // write code here
        int z=0;
        int h=nums.size();
        const int a=1e9+7;
        stack<int> s;
        for(int i=0;i<=h;++i)
        {
            int c=(i==h)?0:nums[i];
            while(!s.empty()&&c<nums[s.top()])
            {
                int f=s.top();
                s.pop();
                int L=f-(s.empty()?-1:s.top());
                int R=i-f;
                z=(z+static_cast<long>(nums[f])*L*R)%a;
            }
                   s.push(i);
        }
                   return z;
    }
};

C 解法, 执行用时: 23ms, 内存消耗: 2628KB, 提交时间: 2022-06-27

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @param numsLen int nums数组长度
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */

// 方法一：动态规划，超时了
// int sumSubarr(int* nums, int numsLen ) {
//     long long result = 0;
//     int dp[numsLen];
//     for (int i = 0; i < numsLen; i++) {
//         dp[i] = nums[i];
//         result = (result + nums[i]) % 1000000007;
//     }
//     for (int d = 2; d <= numsLen; d++) {
//         for (int i = 0; i <= numsLen - d; i++) {
//             dp[i] = dp[i] > dp[i+1] ? dp[i+1] : dp[i];
//             result = (result + dp[i]) % 1000000007;
//         }
//     }
    
//     return result;
// }

// 方法二：单调栈
int sumSubarr(int* nums, int numsLen ) {
    long long result = 0;
    int stack[numsLen], sTop = 0;
    long long v, l, r, minValue, minIndex;
    
    for (int i = 0; i < numsLen; i++) {
        v = nums[i];
        
        while (sTop > 0 && v < nums[stack[sTop - 1]]) {
            minIndex = stack[sTop - 1];
            minValue = nums[stack[sTop - 1]];
            if (sTop - 1 > 0) {
                l = stack[sTop - 2] + 1;
            } else {
                l = 0;
            }
            r = i - 1;
            
            result = (result + (r - minIndex + 1) * (minIndex - l + 1) * minValue) % 1000000007;
                
            sTop--;
        }
        
        stack[sTop++] = i;
    }
    
    while (sTop > 0) {
        minIndex = stack[sTop - 1];
        minValue = nums[stack[sTop - 1]];
        if (sTop - 1 > 0) {
            l = stack[sTop - 2] + 1;
        } else {
            l = 0;
        }
        r = numsLen - 1;

        result = (result + (((r - minIndex + 1) * (minIndex - l + 1) % 1000000007) * minValue) % 1000000007) % 1000000007;

        sTop--;
    }
    
    return result;
}