Leetcode 907. 子数组的最小值之和

题目

Leetcode 907. 子数组的最小值之和

代码（9.20 首刷看解析）

class Solution {
public:
    const long long mod = 1e9+7;
    int sumSubarrayMins(vector<int>& arr) {
        int n = arr.size();
        vector<int> monostack;  // 找每个数作为最小值能有多少子数组符合条件
        vector<int> left(n), right(n);     // 以arr[i]为最小值的左右边界长度
        for(int i = 0; i < n; i++) {
            while(!monostack.empty() && arr[i] <= arr[monostack.back()]) {
                monostack.pop_back();
            }
            left[i] = i - (monostack.empty() ? -1 : monostack.back());  // 栈顶元素为左边第一个小于arr[i]的元素arr[j]
            monostack.push_back(i);
        }
        monostack.clear();
        for(int i = n-1; i >= 0; i--) {
            while(!monostack.empty() && arr[i] < arr[monostack.back()]) {
                monostack.pop_back();
            }
            right[i] = (monostack.empty() ? n : monostack.back()) - i;
            monostack.push_back(i);
        }
        long long ans = 0;
        for(int i = 0; i < n; i++) {
            ans = (ans + (long long)left[i]*right[i]*arr[i])%mod;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29