LeetCode-子数组的最小值之和

给定一个整数数组 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

思路1：纯暴力。找到所有的连续子数组，在每个连续子数组中找到最小值然后相加，数据量已经到了10^4，时间复杂度爆炸。
思路2：每一个值都有一定的有效范围（我称之为“有效范围”），在这个有效范围的跨度内，所有子数组的最小值都是当前值，这事只需要求出这个范围内数组的数量乘以当前值即可。求数组的有效范围，可以转化为求左边更小的数和右边更小的数的问题，当前值的有效范围的边界即为这两个更小的数。求解这个问题就可以使用单调栈来完成。需要进行三次遍历，求左边界数组、求右边界数组以及求解最终结果。
补充：力扣题解中有更优化的单次循环的解法

class Solution {
    public int sumSubarrayMins(int[] arr) {
         if(arr.length == 0){
            return 0;
        }
        //定义记录左边界和右边界的数组，通过单调栈求解数组
        int len = arr.length;
        int[] left = new int[len];
        int[] right = new int[len];
        Deque<Integer> stack = new ArrayDeque<Integer>();

        for(int i = 0; i < len; 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();
		//同上边求left数组的过程
        for(int i = len - 1; i >= 0; i--){
            while(!stack.isEmpty() && arr[stack.peek()] >= arr[i]){
                stack.pop();
            }
            if(stack.isEmpty()){
                right[i] = len;
            }else{
                right[i] = stack.peek();
            }
            stack.push(i);
        }

        //根据有效值和有效范围计算结果
        long res = 0;
        int mod = 1000000007;
        for(int i = 0; i < len; i++){
            res = (res + (long)(i - left[i]) * (right[i] - i) * arr[i]) % mod;
        }
        return (int)res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50