题目描述: 给定一个长度为 n 的数组 nums ,算出他所有的 min(sub) 之和,其中 sub 指数组 nums 的所有连续子数组 , min(sub) 指子数组的最小值。 代码实现:js 测试样例: 输入:[3,1,2,4,5] 返回值:30 说明: 子数组有 3、1、2、4、5、(3,1)、(3,2)、(3,4)、(3,5)、(1,2)、(1,4)、(1,5)、(2,4)、(2,5)、(4,5)、(3,1,2)、(3,1,4)、(3,1,5)、(3,2,4)、(3,4,5)、(1,2,4)、(1,2,5)、(2,4,5)、(3,1,2,4)、(3,1,2,5)、(3,2,4,5)、(1,2,4,5) 其最小值和是 30
时间: 2023-12-28 09:16:21 浏览: 47
以下是 JavaScript 代码实现:
```javascript
function sumOfMinSubArrays(nums) {
const n = nums.length;
const mod = 1e9 + 7;
const stack = []; // 单调栈,存储元素下标
const left = [], right = [];
// 计算 left 数组,left[i] 表示以 nums[i] 为最小值的子数组个数
for (let i = 0; i < n; i++) {
let count = 1;
while (stack.length > 0 && nums[stack[stack.length - 1]] >= nums[i]) {
const j = stack.pop();
count += left[j];
}
left[i] = count;
stack.push(i);
}
stack.length = 0;
// 计算 right 数组,right[i] 表示以 nums[i] 为最小值的子数组个数
for (let i = n - 1; i >= 0; i--) {
let count = 1;
while (stack.length > 0 && nums[stack[stack.length - 1]] > nums[i]) {
const j = stack.pop();
count += right[j];
}
right[i] = count;
stack.push(i);
}
let ans = 0;
for (let i = 0; i < n; i++) {
ans = (ans + nums[i] * left[i] * right[i]) % mod;
}
return ans;
}
```
该算法的时间复杂度为 $O(n)$,空间复杂度为 $O(n)$。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)