子数组的最小值之和【LC907】
给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。
由于答案可能很大，因此 返回答案模 10^9 + 7 。
果然是一天难一天简单呀
暴力【超时】
2022/10/28
class Solution { public int sumSubarrayMins(int[] arr) { long res = 0; int len = arr.length; for (int i = 0; i < len; i++){ int min = Integer.MAX_VALUE; for (int j = i; j < len; j++){ min = Math.min(min,arr[j]); res += min; } } return (int)(res % (int)(1e9+7)); } }
- 复杂度
。时间复杂度：O ( n 2 )
。空间复杂度：O ( 1 )
单调栈
- 思路：使用单调栈用来寻找每个元素左边第一个小于它的位置L以及右边第一个小于等于它的位置R，找到一个最小值为当前元素的最大区间(L,R]，此时该元素对res的贡献为(i-L)*(R-i)*arr[i]
。为什么是(i-L)*(R-i)*arr[i]？
- 在该元素的左边可以选择全部保留或者依次去掉下标为j∈(L,i)的元素的可能性总共有i-L种
- 在该元素的右边可以选择全部保留或者依次去掉下标为j∈(i,R]的元素的可能性总共有R-i种
- 当数组内不存在该元素时，左边界为-1，右边界为数组长度
- 实现
1.寻找left[i]和right[i]单调栈里元素从栈头到栈底的顺序为递减
。初始化left[i] = -1,right[i]= len
。首先将栈内大等于于它的元素弹出，对于栈顶元素而言，此时找到了右边第一个小于等于它的位置
- 将栈顶元素T[st.top()]弹出 right[st.pop()] = i
。然后栈内剩下的元素均小于当前元素，对于当前元素，找到了左边第一个小于它的位置
- left[i] = st.peek()
。最后当前元素压入栈内
2.遍历left[i]和right[i],res+=(i-L)*(R-i)*arr[i]
- 代码
class Solution { public int sumSubarrayMins(int[] arr) { long res = 0; int MOD = (int)(1e9 + 7); int len = arr.length; Deque<Integer> st = new LinkedList<>(); int[] left = new int[len]; int[] right = new int[len]; for (int i = 0; i < len; i++){ left[i] = -1; right[i] = len; while (!st.isEmpty() && arr[st.peekFirst()] >= arr[i]){ right[st.pollFirst()] = i; } if (!st.isEmpty()){ left[i] = st.peekFirst(); } st.addFirst(i); } for (int i = 0; i < len; i++){ res = (res + (long)arr[i]*(i - left[i])*(right[i] - i)) % MOD; } return (int)(res); } }
- 复杂度
。时间复杂度：O ( n )
。空间复杂度：O ( n )
