0907. Sum of Subarray Minimums

题目信息

题号:

0907

难度:

Medium

主题:

数组、连续子数组、最小值求和

原题:

LeetCode 0907

重点:

需要对每个非空连续子数组分别取最小值并累加;相同内容出现在不同下标范围时仍属于不同子数组

题目重述

给定正整数数组 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。