阳光明媚

3妹：“太阳当空照，花儿对我笑，小鸟说早早早，你为什么背上炸药包”
2哥 :3妹，什么事呀这么开发。
3妹：2哥你看今天的天气多好啊，阳光明媚、万里无云、秋高气爽，适合秋游。
2哥：是啊，立冬之后天气多以多云为主，好不容易艳阳高照。可是你不能秋游，赶紧收拾收拾上班去啦
3妹：哼， 好吧~
2哥：给你出了一道题发你微信里了， 上班通勤的路上记得看一下，回来问你答案~

image.png
3妹：知道啦，难不倒我！

题目：

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

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

示例 1：

输入：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。
示例 2：

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

提示：

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

思路：

思考

单调栈,
考虑所有满足以数组 arr中的某个元素 arr[i]为最右且最小的元素的子序列个数 C[i]，那么题目要求求连续子数组的最小值之和即为 ∑arr[i]×C[i]，其中数组 arr的长度为 n。
我们必须假设当前元素为最右边且最小的元素，这样才可以构造互不相交的子序列，否则会出现多次计算，因为一个数组的最小值可能不唯一。

java代码：

class Solution {
    public int sumSubarrayMins(int[] arr) {
        int n = arr.length;
        Deque<Integer> monoStack = new ArrayDeque<Integer>();
        int[] left = new int[n];
        int[] right = new int[n];
        for (int i = 0; i < n; i++) {
            while (!monoStack.isEmpty() && arr[i] <= arr[monoStack.peek()]) {
                monoStack.pop();
            }
            left[i] = i - (monoStack.isEmpty() ? -1 : monoStack.peek());
            monoStack.push(i);
        }
        monoStack.clear();
        for (int i = n - 1; i >= 0; i--) {
            while (!monoStack.isEmpty() && arr[i] < arr[monoStack.peek()]) {
                monoStack.pop();
            }
            right[i] = (monoStack.isEmpty() ? n : monoStack.peek()) - i;
            monoStack.push(i);
        }
        long ans = 0;
        final int MOD = 1000000007;
        for (int i = 0; i < n; i++) {
            ans = (ans + (long) left[i] * right[i] * arr[i]) % MOD; 
        }
        return (int) ans;
    }
}