0907. Sum of Subarray Minimums¶
题目信息¶
- 题号:
0907
- 难度:
Medium
- 主题:
数组、连续子数组、最小值求和
- 原题:
- 重点:
需要对每个非空连续子数组分别取最小值并累加;相同内容出现在不同下标范围时仍属于不同子数组
题目重述¶
给定正整数数组 arr。枚举数组的所有非空连续子数组,对每个子数组取其中的最小元素,再把这些最小值全部相加。
请返回所得总和对 10^9 + 7 取模后的结果。子数组由起止下标确定,即使两个子数组包含的数值序列相同,只要位置不同也要分别计数。
1 <= arr.length <= 3 * 10^4,1 <= arr[i] <= 3 * 10^4。
自建示例¶
最小值由中间元素重复贡献:
输入:arr = [2,1,3]
输出:9
解释:六个非空子数组 [2]、[1]、[3]、[2,1]、[1,3]、[2,1,3] 的最小值依次为 2、1、3、1、1、1,总和为 9。
数组只有一个元素:
输入:arr = [5]
输出:5
解释:唯一的非空连续子数组是 [5],其最小值为 5,因此总和也是 5。