题目:
给定一个整数数组 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 * 104
1 <= arr[i] <= 3 * 104
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/sum-of-subarray-minimums
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路:
先记录一下我没通过的解题思路:
我想利用双循环来解题,外层循环表示从连续子数组的开始,内层循环表示连续子数组的结束,这样数组中的每个单个元素也能相加,遍历过程中也能更新最小值,以及得到求和,最后将和与10^9 + 7取模即可。
但是用例过不去,我还找不出来原因,哭了我这个小垃圾~
问题代码:
1 class Solution { 2 public int sumSubarrayMins(int[] arr) { 3 int sum = 0, n = arr.length; 4 for(int i = 0; i < n; i++){ 5 sum += arr[i]; 6 int min_num = arr[i]; 7 for(int j = i + 1; j < n; j++){ 8 if(arr[j] > min_num){ 9 sum += min_num; 10 }else{ 11 sum += arr[j]; 12 min_num = Math.min(min_num, arr[j]); 13 } 14 } 15 } 16 int MOD = 1_000_000_007; 17 return (int)(sum % MOD); 18 } 19 }
参考评论区的各位大佬,得到以下题解~
单调栈+贡献法:
①贡献法:
例如:[1,4,2,3,1]中2是子数组[2]、[4,2]、[2,3]、[4,2,3]的最小值,那么2对答案的贡献就是2*4 = 8。
由于以2为连续子数组中的最小值,那么连续子数组中就不能包含比2小的数,因此就可以找到2左右两侧比它小的数的下标,这样就可以确定以2为最小值的连续子数组的边界范围。左右两边比2小的边界范围在(0,4),闭区间为[1,3]。
设arr[i]对应的边界为开区间(L,R),子数组需要包含arr[i],故:
- 左边的下标可以是:L, L+1, L+2,...,i,一共有i-L个;
- 右边的下标可以是:i,i+1,i+2,...,R-1,一共有R-i个;
在arr中不含重复元素的前提下,以arr[i]为最小值的数组个数为 (i-L)*(R-i) ,对答案的贡献值为 arr[i] *(i-L)*(R-i) (类比:上衣有n件,裤子有m条,则一共有 n * m中搭配方法)。注意:如果左侧没有比 arr[i]小的元素,则L= -1,如果右侧没有比 arr[i]小的元素,则R= n,
如果arr中包含重复元素,例如[1,2,4,2,3,1],第一个2和第二个2对应的边界为(0,5),都包含了子数组[2,4,2,3],这样就会计算同一个子数组。
这样需要修改一下边界的定义,将左边界改为小于等于arr[i]的元素下标,右边界依然为小于arr[i]的元素下标,那么:第一个2对应的边界为(0,5),第二个2对应的边界为(1,5)。
单调栈:参考@【爪哇缪斯L5】:https://leetcode.cn/problems/sum-of-subarray-minimums/solution/-by-muse-77-367z/
构建一个单调递增的栈,里面存放的是元素的下标,如果栈为空,那么直接入栈,如果栈不为空,则进行如下操作:
- 如果 栈顶元素对应的值 >= arr[i]:就弹出栈顶元素,直到栈为空或者栈顶元素对应的值更小,此时栈顶就是最近更小值的位置,即为左边界,即(新的栈顶元素, i),反过来想想,对于每个出栈的元素,当前元素arr[i]就是向右比它更小的第一个元素,这样也就得到右边界(结合下面的图解进行理解);
- 如果 栈顶元素对应的值 < arr[i]:则arr[i]直接入栈
例如:
当遍历完整个数组以后,栈中仍然还存在元素,让剩下元素出栈,根据题目中【提示】部分描述,1 <= arr[i] <= 3 * 10^4,所以,arr数组中所有元素都是大于0的,那么我们就虚拟一个元素将其放入堆栈中,因为堆栈中所有元素的值都大于0,所以也就都会被执行出栈操作了。
java代码:
1 class Solution { 2 private static final long MOD = 1000000007; 3 public int sumSubarrayMins(int[] arr) { 4 long ans = 0; 5 Deque<Integer> stack = new ArrayDeque<>(); 6 //最左边界哨兵入栈,-1是索引 7 stack.push(-1); 8 for(int i = 0; i <= arr.length; i++){ 9 //添加末尾哨兵,已经超过数组长度 10 //则设一个虚拟哨兵索引为n对应的值为0,方便剩余元素出栈 11 int m = i < arr.length ? arr[i] : 0; 12 while(stack.size() > 1 && arr[stack.peek()] >= m){ 13 int r = stack.pop(); 14 //当前栈顶的贡献值 15 //(栈顶-弹出后的栈顶)*(当前值的下标-弹出栈顶) 16 ans += (long) arr[r] * (r - stack.peek()) * (i - r); 17 } 18 stack.push(i); 19 } 20 return (int)(ans % MOD); 21 } 22 }