907. 子数组的最小值之和

907. 子数组的最小值之和

原始题目链接：https://leetcode.cn/problems/sum-of-subarray-minimums/

给定一个整数数组 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（元素本身作为子数组），所以遍历数组，统计个数然后加和。

代码实现：

class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        # 单调栈：（当前元素，当前元素作为最小值的子数组个数）
        stack = []
        # 当前元素最小值对总和的增益
        count = 0
        res = 0

        # 遍历数组
        for num in arr:
            # 当前元素作为最小值的子数组个数至少为1，即子数组元素只有一个且为本身
            value = 1
            # 遍历栈，看当前元素是否比小于之前的元素
            # 如果有，则开始计算当前这个元素作为最小元素的所有子数组的和，
            # 则把元素弹出栈，因为使用了同一个变量count来存储相同元素的子数组的和，
            # 为了不重复，就需要减掉之前元素对总和的影响（清空count）
            # 把当前元素作为最小值的子数组个数+1
            while stack and num <= stack[-1][0]:
                pre_num, pre_count = stack.pop()
                count -= pre_count * pre_num
                value += pre_count

            stack.append((num, value))
            count += num * value
            res += count
            res %= 1000000007
            

        return res

参考文献：
https://leetcode.cn/problems/sum-of-subarray-minimums/solution/python3dan-diao-zhan-by-deyangdeyang-blge/