题目
给定一个整数数组
arr，找到min(b)的总和，其中b的范围为arr的每个（连续）子数组。由于答案可能很大，因此 返回答案模
10^9 + 7。
解题思路
- 找到以当前值为最小值所能组成的子数组；
- 若存在两个相同元素则左右边界只允许包含一边，否则会重复计算中间区域；
- 在每次计算后对10^9 + 7取余。
代码展示
class Solution { public int sumSubarrayMins(int[] arr) { int MOD = 1000000007; int n = arr.length; long ans = 0L; for (int i = 0; i < n; i++){ int num = arr[i]; //左右两侧只允许一侧可以等于当前值，否则会重复计算中间值 //遍历左侧 int left = i - 1; for ( ; left >= 0; left--){ if(arr[left] <= num){ break; } } //遍历右侧 int right = i + 1; for ( ; right < n; right++){ if(arr[right] < num){ break; } } ans = (ans + (long)(i - left) * (long)(right - i) * num) % MOD; } return (int) ans; } }
