![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLiAnYldHL0FWby9mZvwFN4ETMfdHLkVGepZ2XtxSZ6l2clJ3LcV2Zh1Wa9M3clN2byBXLzN3btgHL9s2RkBnVHFmb1clWvB3MaVnRtp1XlBXe0xCMy81dvRWYoNHLwEzX5xCMx8FesU2cfdGLwMzX0xiRGZkRGZ0Xy9GbvNGLpZTY1EmMZVDUSFTU4VFRR9Fd4VGdsQTMfVmepNHLrJXYtJXZ0F2dvwVZnFWbp1zczV2YvJHctM3cv1Ce-cmbw5yMyAjM4EDN3YDZ3Y2NyIWNzYzXxEzM1gDM4IzLcBTMyIDMy8CXn9Gbi9CXzV2Zh1WavwVbvNmLvR3YxUjLyM3Lc9CX6MHc0RHaiojIsJye.png)
题目
给定一个整数数组 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
题解
解题思路
单调栈 + 计算每一个元素对答案的贡献值。
/**
* @param {number[]} arr
* @return {number}
*/
var sumSubarrayMins = function(arr) {
// 维护一个严格单调递增的栈,栈中存下标
const stack = [];
const left = [];
const right = [];
const len = arr.length;
const mod = 1_000_000_007;
let ans = 0;
for(let i = 0; i < len; i++) {
// 一个需要等于
while(stack.length && arr[stack[stack.length-1]] >= arr[i]) {
stack.pop();
}
const top = stack[stack.length-1] ?? -1;
stack.push(i);
left.push(top + 1);
}
stack.length = 0;
for(let i = len-1; i >= 0; i--) {
// 一个不能等于
while(stack.length && arr[stack[stack.length-1]] > arr[i]) {
stack.pop();
}
const top = stack[stack.length-1] ?? len;
stack.push(i);
right.push(top - 1);
}
right.reverse();
// console.log(left);
// console.log(right);
for(let i = 0; i < len; i++) {
const subArrLen = (i - left[i] + 1) * (right[i] - i + 1);
const contribution = subArrLen % mod * arr[i] % mod;
// console.log(subArrLen, arr[i], contribution);
ans = (ans + contribution) % mod;
}
return ans;
};