题目描述
给定一个整数数组 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 = [71,55,82,55]
输出:593
提示
1 <= arr.length <= 3 * 10^4
1 <= arr[i] <= 3 * 10^4
算法1
(单调栈)
- 如果枚举每个区间的左右端点,时间复杂度为$O(n^2)$,显然是过不去的,所以我们转换一下思路:考虑每个位置对答案的贡献
- 对于下标为
i
的元素a[i]
,找到左侧第一个比a[i]
小的元素,下标记为l[i]
,如果没有就设置为-1
;右侧第一个比a[i]
大的元素,下标记为r[i]
,如果没有就记为n
,即左侧有i - l[i]
个数可以选,右侧有r[i] - i
个数可以选,根据乘法原理,所以a[i]
对答案的贡献为a[i] * (i - l[i]) * (r[i] - i)
,对于找到两侧第一个比a[i]
小的元素,可以用单调栈来解决 -
怎么解决重复计数问题:如
[71, 55, 82, 55]
,在计算55
的贡献时,多个子数组会被重复计算。 我们只需要在计算a[i]
左右侧第一个最小元素的时候,在左侧或者右侧考虑小于等于a[i]
的元素即可:对于第一个55
,l = -1, r = 4
,对于第二个55
,l = 1, r = 4
,这样在处理第二个55
的时候,不会把包含第一个55
的子数组计算在内 -
时间复杂度:$O(n)$
- 空间复杂度:$O(n)$
Java 代码
class Solution {
public int sumSubarrayMins(int[] arr) {
int n = arr.length;
Deque<Integer> stk = new ArrayDeque<>();
int[] l = new int[n];
int[] r = new int[n];
for(int i = 0; i < n; i++){
while(stk.size() > 0 && arr[stk.peek()] > arr[i]) stk.pop();
l[i] = stk.size() == 0 ? -1 : stk.peek();
stk.push(i);
}
stk.clear();
for(int i = n - 1; i >= 0; i--){
while(stk.size() > 0 && arr[stk.peek()] >= arr[i]) stk.pop();
r[i] = stk.size() == 0 ? n : stk.peek();
stk.push(i);
}
long res = 0;
int mod = (int)1e9 + 7;
for(int i = 0; i < n; i++){
res = (res + (long)arr[i] * (i - l[i]) * (r[i] - i)) % mod;
}
return (int)res;
}
}