05 August 2008
给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。
由于答案可能很大，因此 返回答案模 10^9 + 7 。
1
2
3
4
5
输入：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。
最朴素也是最直观的解法，既然让我们要求每个子数组的最小值，那么直接枚举出所有子数组即可。两层循环，外层控制子数组的起始位置，内层控制子数组的结束位置。然后求出每个数组的最小值，求和即可。
O(n^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
private static final int MOD = 1000000007;
public int sumSubarrayMins(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int n = arr.length;
long result = 0;
// 起点
for (int i = 0; i < n; i++) {
int min = arr[i];
// 终点
for (int j = i; j < n; j++) {
min = Math.min(min, arr[j]);
result = (result + min) % MOD;
}
}
return (int) result;
}
}
根据上面的O(n^2)暴力解法，我们需要优化时间复杂度。如何优化呢？
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
class Solution {
private static final int MOD = 1000000007;
public int sumSubarrayMins(int[] arr) {
// 处理边界情况
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++) {
// 向左找第一个小于等于E的元素
while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
stack.pop();
}
// 设立一个最左边界-1
if (stack.isEmpty()) {
left[i] = -1;
} else {
left[i] = stack.peek();
}
// 下标入栈，方便同时得到i和A[i]
stack.push(i);
}
// 第二次循环找到所有元素的右边界
stack.clear();
for (int i = n - 1; i >= 0; i--) {
// 向右找第一个小于E的元素
while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
stack.pop();
}
// 设立一个最右边界n
if (stack.isEmpty()) {
right[i] = n;
} else {
right[i] = stack.peek();
}
// 下标入栈，方便同时得到i和A[i]
stack.push(i);
}
// 按照贡献度计算即可
// 注意此处left[i]和right[i]实际上记录的是左边界-1和右边界+1，和上面思路中有些区别，便于计算
long result = 0;
for (int i = 0; i < n; i++) {
result = (result + (long) (i - left[i]) * (right[i] - i) * arr[i]) % MOD;
}
return (int) result;
}
}
上面代码逻辑比较清晰，但是经历了两次遍历且用到了额外空间，我们可以用更简洁的一次遍历来直接求出所有元素的左边界和右边界，并且不用额外空间。
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
class Solution {
private static final int MOD = 1000000007;
// 重写根据下标取值方法，-1和n返回MIN_VALUE
private int getElement(int[] arr, int n, int i) {
if (i == -1 || i == n) {
return Integer.MIN_VALUE;
}
return arr[i];
}
public int sumSubarrayMins(int[] arr) {
// 处理边界情况
if (arr == null || arr.length == 0) {
return 0;
}
int n = arr.length;
long result = 0;
Deque<Integer> stack = new LinkedList<>();
// 将下标-1和n作为两个哨兵元素，它们对应的元素为MIN_VALUE
// -1作为最左边界，n作为最右边界
for (int i = -1; i <= n; i++) {
// 向左寻找第一个小于等于A[i]的元素
while (!stack.isEmpty() && getElement(arr, n, stack.peek()) > getElement(arr, n, i)) {
// A[cur]就是之前思路中的A[i]，注意区分和上面代码的区别
// 对于每个出栈元素来说，i就是它们的右边界，而栈顶元素就是左边界
int cur = stack.pop();
// 计算贡献值
result = (result + (long) (cur - stack.peek()) * (i - cur) * arr[cur]) % MOD;
}
stack.push(i);
}
return (int) result;
}
}