![image-20230316113719671](https://img.slcp.top/image-20230316113719671.png)

## 解题思路
使用单调栈的套路找到每个元素左右离着最近的比自己小的值。`x`作为最小值 子数组范围`(L..x..R)`，`x`位置左边比自己小最近的是`L`，右边比自己小最近的是`R`。所有子数组都要通过`x`，所以一共有` x-(L+1)-1 `个元素通过`x`，由于L和R位置到不了，所以左边从`L+1`开始，右边到`R-1`。右边子数组可到达的长度` (R-1)-x+1 `，所以以x作为最小值，子数组的个数为` (x-L)*(R-x) `个，就是`x`左边的长度` * x`右边的长度，左右都包含`x`本身。以`x`作为最小值，所有子数组的累加和`=arr[x] * (x-L) * (R-x)`

> 复杂度分析
时间复杂度：`O(n)`，`n`为`arr`数组的长度。
空间复杂度：`O(n)`

## 代码
~~~java
class Solution {
    public int sumSubarrayMins(int[] arr) {
        int mod = 1000000007;
        int N = arr.length;
        int[] stack = new int[N];
        int si = -1;
        long sum = 0;
        for (int i = 0; i < N; i++) {
            while (si != -1 && arr[stack[si]] >= arr[i]) {
                int j = stack[si--];
                long a = j - (si == -1 ? -1 : stack[si]);
                long b = i - j;
                sum += a * b * (long)arr[j];
                sum %= mod;
            }
            stack[++si] = i;
        }
        while (si != -1) {
            int j = stack[si--];
            long a = j - (si == -1 ? -1 : stack[si]);
            long b = N - j;
            sum += a * b * (long)arr[j];
            sum %= mod;
        }
        return (int) sum;
    }
}
~~~

907. 子数组的最小值之和

目录