Leetcode 907.子数组的最小值之和（中等）

一、题目

1、题目描述

给定一个整数数组 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。
1
2
3
4
5

示例2：

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

2、基础框架

class Solution {
public:
    int sumSubarrayMins(vector<int>& arr) {

    }
};
1
2
3
4
5
6

3、原题链接

907.子数组的最小值之和

二、解题报告

1、思路分析

整体思路：

求的以每个位置的值为最小值能得到的子数组个数。

流程：
假设 10 位置是 7， 左边离它最近比它小的是 5 位置的 5，右边离它最近比它小的是 15 位置的 4。那么以 7 作为最小值的子数组范围为 6 ~ 14，但这个范围中并不是所有的子数组都是以 7 作为最小值的，比如假设 6 位置是 10， 7 位置是 8，那么6位置作为子数组最小值是10，7位置作为子数组的最小值是8，所以必须要跨过 10 位置的 7 的子数组才是以 7 作为最小值的。

示例：

以 6 位置开头的：6 ~ 10、6 ~ 11、6 ~ 12、6 ~ 13、6 ~ 14 这些都是以 7 作为最小值的子数组。

同理还有 7 位置开头的，8 位置开头的，9 位置开头的，10 位置开头的子数组。

那么整体数量是多少呢？

6 ~ 10 共 5 个数，10 ~ 14 共 5 个数，所以总的以 7 为最小值的子数组个数为 5 * 5 = 25 个，产生的子数组最小值累加和为 25 * 7 = 175。

抽象化：
$i$ 位置的 $x$​，左边离它最近的是比它小的 $k$ 位置的 $y$​， 右边离它最近比它小的是 $j$ 位置的 $z$​，以 $x$ 为最小值的范围为 $(k,j)$，那么产生以 $x$ 为最小值的子数组数量为 $(i-k)\ast (j-i)$​，以 $i$ 位置的 $x$ 值为最小值产生的子数组的累加和为 $(i-k)\ast (j-i)\ast x$
​
有重复值的情况需要改进：

数组：2 4 5 3 6 6 6 3 7 8 6  3  5  3  2
下标：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
		                   
那么以 3 位置的 3 作为最小值，能扩充的范围为 1 ~ 6, 产生的子数组为：
       1 ~ 3，1 ~ 4, 1 ~ 5，1 ~ 6
    	 2 ~ 3，2 ~ 4, 2 ~ 5, 2 ~ 6
    		3 ~ 3, 3 ~ 4, 3 ~ 5, 3 ~ 6
而 7 位置的 3 作为最小值，能扩充的范围为 1 ~ 10，所以产生的子数组为：
     1 ~ 7， 1 ~ 8， 1~ 9, 1 ~ 10
    	2 ~ 7， 2 ~ 8， 2 ~ 9， 2 ~ 10
    		......
    		7 ~ 7, 7 ~ 8, 7 ~ 9,  7 ~ 10
    注意，这个3是包含了前面的3的范围的
1
2
3
4
5
6
7
8
9
10
11
12
13

就是子数组的结尾处在相等位置的时候停住，目的是为了去重。

同理，也可以在左边值相等的时候停住：

2、时间复杂度

$O(n)$

3、代码详解

C++版

class Solution {
public:
    int sumSubarrayMins(vector<int>& arr) {
        if (arr.size() == 0) return 0;

        long ans = 0;
        int left[arr.size()];
        int right[arr.size()];
        memset(left, 0, sizeof(left));
        memset(right, 0, sizeof(right));
        nearLessLeftAndLessEqualRight(arr, left, right);
        
        for (int i = 0; i < arr.size(); i++) {
            int start = i - left[i]; //子数组起点个数
            int end = right[i] - i; //子数组终点个数
            ans += start * end * (long) arr[i];
            ans %= 1000000007;
        }

        return ans;
    }

	// 左边 < arr[i], 右边 <= arr[i] 的位置构成的范围
    void nearLessLeftAndLessEqualRight(vector<int> &arr, int *left, int *right) {
        int n = arr.size();
        int _stack[n];
        int si = -1;

        for (int i = 0; i < n; i++) {
            while (si != -1 && arr[_stack[si]] >= arr[i]) {
                int cur = _stack[si--];
                left[cur] = si == -1 ? -1 : _stack[si];
                right[cur] = i;
            }
            _stack[++si] = i;
        }

        while (si != -1) {
            int cur = _stack[si--];
            left[cur] = si == -1 ? -1 : _stack[si];
            right[cur] = n;
        }
    }
};
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

Java版

// 测试链接：https://leetcode.com/problems/sum-of-subarray-minimums/
// subArrayMinSum1是暴力解
// subArrayMinSum2是最优解的思路
// sumSubarrayMins是最优解思路下的单调栈优化
// Leetcode上不要提交subArrayMinSum1、subArrayMinSum2方法，因为没有考虑取摸
// Leetcode上只提交sumSubarrayMins方法，时间复杂度O(N)，可以直接通过
public class SumOfSubarrayMinimums {

	public static int subArrayMinSum1(int[] arr) {
		int ans = 0;
		for (int i = 0; i < arr.length; i++) {
			for (int j = i; j < arr.length; j++) {
				int min = arr[i];
				for (int k = i + 1; k <= j; k++) {
					min = Math.min(min, arr[k]);
				}
				ans += min;
			}
		}
		return ans;
	}

	// 没有用单调栈
	public static int subArrayMinSum2(int[] arr) {
		// left[i] = x : arr[i]左边，离arr[i]最近，<=arr[i]，位置在x
		int[] left = leftNearLessEqual2(arr);
		// right[i] = y : arr[i]右边，离arr[i]最近，< arr[i],的数，位置在y
		int[] right = rightNearLess2(arr);
		int ans = 0;
		for (int i = 0; i < arr.length; i++) {
			int start = i - left[i]; //i位置左边能扩充的范围中的数字个数
			int end = right[i] - i; //i位置右边能扩充的范围中的数字个数
			ans += start * end * arr[i];
		}
		return ans;
	}

	public static int[] leftNearLessEqual2(int[] arr) {
		int N = arr.length;
		int[] left = new int[N];
		for (int i = 0; i < N; i++) {
			int ans = -1;
			for (int j = i - 1; j >= 0; j--) {
				if (arr[j] <= arr[i]) {
					ans = j;
					break;
				}
			}
			left[i] = ans;
		}
		return left;
	}
	
	// 比如两个位置的3，后一个位置的3往左边扩充的区域到前一个位置的3停止（到不了）
	public static int[] rightNearLess2(int[] arr) {
		int N = arr.length;
		int[] right = new int[N];
		for (int i = 0; i < N; i++) {
			int ans = N;
			for (int j = i + 1; j < N; j++) {
				if (arr[i] > arr[j]) {
					ans = j;
					break;
				}
			}
			right[i] = ans;
		}
		return right;
	}

    //O(n)
	public static int sumSubarrayMins(int[] arr) {
		int[] stack = new int[arr.length];
		int[] left = nearLessEqualLeft(arr, stack);//每个位置左边离它最近 <= 它的位置
		int[] right = nearLessRight(arr, stack); 每个位置右边离它最近 < 它的位置
		long ans = 0;
		for (int i = 0; i < arr.length; i++) {
			long start = i - left[i];
			long end = right[i] - i;
			ans += start * end * (long) arr[i];
			ans %= 1000000007;
		}
		return (int) ans;
	}

	public static int[] nearLessEqualLeft(int[] arr, int[] stack) {
		int N = arr.length;
		int[] left = new int[N];
		int size = 0;
		for (int i = N - 1; i >= 0; i--) {
			while (size != 0 && arr[i] <= arr[stack[size - 1]]) {
				left[stack[--size]] = i;
			}
			stack[size++] = i;
		}
		while (size != 0) {
			left[stack[--size]] = -1;
		}
		return left;
	}

	public static int[] nearLessRight(int[] arr, int[] stack) {
		int N = arr.length;
		int[] right = new int[N];
		int size = 0;
		for (int i = 0; i < N; i++) {
			while (size != 0 && arr[stack[size - 1]] > arr[i]) {
				right[stack[--size]] = i;
			}
			stack[size++] = i;
		}
		while (size != 0) {
			right[stack[--size]] = N;
		}
		return right;
	}

	public static int[] randomArray(int len, int maxValue) {
		int[] ans = new int[len];
		for (int i = 0; i < len; i++) {
			ans[i] = (int) (Math.random() * maxValue) + 1;
		}
		return ans;
	}

	public static void printArray(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

	public static void main(String[] args) {
		int maxLen = 100;
		int maxValue = 50;
		int testTime = 100000;
		System.out.println("测试开始");
		for (int i = 0; i < testTime; i++) {
			int len = (int) (Math.random() * maxLen);
			int[] arr = randomArray(len, maxValue);
			int ans1 = subArrayMinSum1(arr);
			int ans2 = subArrayMinSum2(arr);
			int ans3 = sumSubarrayMins(arr);
			if (ans1 != ans2 || ans1 != ans3) {
				printArray(arr);
				System.out.println(ans1);
				System.out.println(ans2);
				System.out.println(ans3);
				System.out.println("出错了！");
				break;
			}
		}
		System.out.println("测试结束");
	}
}
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155