![](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;
};