907. 子数组的最小值之和

题目分析：最朴素的想法，自然是枚举所有子数组，然后找出所有子数组中元素最小值，最后进行累加即可。
在进一步讨论问题之前，我们先观察数据，然后引入辐射范围的定义。
假设给定数据，{3，1，2，4，1}，如下图所示：

对于arr[0]=3而言，其辐射范围为1。

对于arr[1]=1而言，其辐射范围为5。

如果有子数组包含元素1的话，那么最小值必然是1，所以这个子数组就是元素1的辐射范围。
对于arr[1]=1而言，其辐射的子数组有{1}，{3,1}，{3,1,2}，{3,1,2,4}，{3,1,2,4,1}，{1,2}，{1,2,4}，{1,2,4,1}。

因此，我们可以把辐射范围定义为：当前元素arr[i]所辐射的子数组数量。
我们可以把原问题转化为：求解数组arr中每一个元素的辐射范围与自身值的乘积，最后累加起来即为答案。我们假设每个元素的辐射范围为len[i]，完整的公式为：

那么现在待解决的问题就转变为如何求解每一个元素的辐射范围。
我们有一个朴素的思想，对于nums[i]，我们分别向两边搜索（即向左和向右），找到第一个小于nums[i]的数，分别记为left[i]和right[i]。这样一来，我们可以利用子数组左边界的取值范围[left[i], i]和子数组右边界的取值范围[i, right[i]]来确定子数组的数量，即当前元素的辐射范围。
在这里遇到的一个坑，本来子数组的数量应该为（i - left[i] + 1）* (right[i] - i + 1)，但在实现时却变成了（i - left[i]）* (right[i] - i)，
这是因为我们在向右搜索时，只要遇到了比当前元素nums[i]小的元素（记为nums[k]）才会停止，这是下标指向为k，但是我们的真正的取值范围在[i, k-1]（因为nums[k]<nums[i]），即右边界的取值数量为：(k - 1 - i + 1)=(k - i)，所以在这里做了一下坐标带入，即真正的right[i]=k-1，将其待入(right[i] - i + 1)=((k - 1) - i + 1)=(k - i)。

class Solution {
    public int sumSubarrayMins(int[] arr) {
        int mod = (int) 1e9 + 7;
        if(arr == null || arr.length == 0){
            return 0;
        }
        int n = arr.length;
        int[] left = new int[n];
        int[] right = new int[n];
        Deque<Integer> stack = new LinkedList<>();
        for(int i = 0; i < n; i++){
            while(!stack.isEmpty() && arr[stack.peek()] >= arr[i]){ //这里要取等号
                stack.pop();
            }
            if(stack.isEmpty()){
                left[i] = -1;
            }else{
                left[i] = stack.peek();
            }
            stack.push(i);
        }
        stack.clear();
        for(int i = n - 1; i >= 0; i--){
            while(!stack.isEmpty() && arr[stack.peek()] > arr[i]){
                stack.pop();
            }
            if(stack.isEmpty()){
                right[i] = n;
            }else{
                right[i] = stack.peek();
            }
            stack.push(i);
        }
        long ans = 0;
        for(int i = 0; i < n; i++){
            ans = (ans + (long)(i - left[i]) * (right[i] - i) * arr[i]) % mod;
        }
        return (int)ans;
    }
}