西安手机网站制作公司网站制作400哪家好

题目

给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。

由于答案可能很大，因此 返回答案模 10^9 + 7 。

解题思路

1. 找到以当前值为最小值所能组成的子数组；
2. 若存在两个相同元素则左右边界只允许包含一边，否则会重复计算中间区域；
3. 在每次计算后对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;}
}