[数据结构与算法]LeetCode 907. 子数组的最小值之和

单调栈
对于一个数arr[i]来说，可以和左边的数组成数组，可以和右边的数组成数组，也可以同时和左右两边的数组成数组。通过分析可以发现，若在(l, r)（左闭，右闭）范围内的子数组中最小值为arr[i]（即arr[l] < arr[i] 且 arr[r] < arr[i]），则以arr[i]为最小值的子数组数量为(i - l) * (r - l)（可以通过计算得出）

那么这个题的思路就有了，对于一个数arr[i]分别寻找以arr[i]为最小值的左右两侧下标为。以arr[i]为右端点时以，确定子数组范围，以arr[i]为左端点以arr[i]为最小值时的左侧左侧下标，然后相乘得出arr[i]为最小值的次数，然后乘arr[i]得到arr[i]为最小值的和。

这个题的难点在与如何寻找左右两侧的长度，使用暴力搜索将会导致超时

这里使用单调栈来加速长度的求解。可以使用单调栈的原因是，（以arr[i]为右端点为例）如果j > i 且 arr[i] > arr[j]则以arr[i]为最小值的子数组arr[j]一定是最小（因为arr[j] < arr[i]），这样就可以不必重复运算。如果j > i 且 arr[i] < arr[j]则对于arr[j]左侧最长一定是到i

class Solution {
public:
    int sumSubarrayMins(vector<int>& arr) {
        long long MOD = 1e9 + 7;
        int res = 0;
        int n = arr.size();
        vector<int> right(n, 0);
        stack<int> sta;
        // 计算右侧长度
        for(int i = n - 1; i >= 0; i--)
        {
        	// 单调栈维护
            while(!sta.empty() && arr[sta.top()] > arr[i])
                sta.pop();
            right[i] = sta.empty() ? n - i : sta.top() - i;
            sta.push(i);
        }

        while(!sta.empty()) sta.pop();
        
        // 计算左侧长度
        for(int i = 0; i < n; i++)
        {
            while(!sta.empty() && arr[sta.top()] >= arr[i])
                sta.pop();
           	// left 为 long long 进行乘法运算时int溢出	i + 1 == i - (-1)
            long long left = sta.empty() ? i + 1 : i - sta.top();
            // 计算出左侧后，再乘上之前求出的右侧长度，可以得到arr[i]为min时的和
            res = (res + ((left * right[i]) * arr[i]) % MOD) % MOD;
            sta.push(i);
        }
        return res;
    }
};