题目描述

给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。

由于答案可能很大，因此 返回答案模 10^9 + 7。

样例

输入：arr = [3,1,2,4]
输出：17
解释：
子数组为 [3]，[1]，[2]，[4]，[3,1]，[1,2]，[2,4]，[3,1,2]，[1,2,4]，[3,1,2,4]。 
最小值为 3，1，2，4，1，1，2，1，1，1，和为 17。

输入：arr = [11,81,94,43,3]
输出：444

注意

• 1 <= arr.length <= 3 * 10^4
• 1 <= arr[i] <= 3 * 10^4

算法

(单调栈) $O(n)$

1. 转变思路，统计每个位置的数字贡献的答案是多少。
2. 对于每个位置 i，求出最大的 l[i]，满足 A[l[i]] <= A[i]，如果不存在则 l[i] = -1；
3. 同理，求出最小 r[i]，满足 A[r[i]] < A[i]，如果不存在则 r[i] = n;
4. 这样，每个位置贡献的答案就是，A[i] * (r[i] - i) * (i - l[i])。
5. 求 l[i] 和 r[i] 可以用单调栈在线性时间内完成。
6. 具体地，维护一个单调递增（不降）的栈，每次新插入数字前，比较栈顶，如果不满足要求则栈顶出栈，并更新对应的 l[i] (r[i]) 数组即可；最后当前数字的下标入栈。

时间复杂度

• 仅遍历数组若干次，故时间复杂度为 $O(n)$。

空间复杂度

• 需要额外的栈和数组，故空间复杂度为 $O(n)$。

C++ 代码

#define LL long long

class Solution {
public:
    int sumSubarrayMins(vector<int>& arr) {
        const int n = arr.size();
        const int mod = 1000000007;

        stack<int> s;
        vector<int> l(n), r(n);

        for (int i = 0; i < n; i++) {
            while (!s.empty() && arr[i] < arr[s.top()]) {
                r[s.top()] = i;
                s.pop();
            }
            s.push(i);
        }

        while (!s.empty()) {
            r[s.top()] = n;
            s.pop();
        }

        for (int i = n - 1; i >= 0; i--) {
            while (!s.empty() && arr[i] <= arr[s.top()]) {
                l[s.top()] = i;
                s.pop();
            }
            s.push(i);
        }

        while (!s.empty()) {
            l[s.top()] = -1;
            s.pop();
        }

        LL ans = 0;

        for (int i = 0; i < n; i++)
            ans = (ans + (LL)(arr[i]) * (r[i] - i) * (i - l[i])) % mod;

        return ans;
    }
};