博客

题目描述：

给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。

由于答案可能很大，因此 返回答案模 10^9 + 7 。

来源：力扣（LeetCode）

链接：https://leetcode.cn/problems/sum-of-subarray-minimums

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

暴力法：

因为我们要求的是子数组的最小值之和，所以我们只需要遍历数组得出其所有子集然后在针对每个子集求出对应子集的最小值的和即能够得到最终解。

代码：

# 暴力法
class Solution:
    def sumSubarrayMins(self, arr: list[int]) -> int:
        len_arr = len(arr)
        result = []
        for i in range(len_arr):
            for j in range(i + 1, len_arr + 1):
                result.append(arr[i:j])
        product = self.minvalue(result)
        return product

    def minvalue(self, result):
        product = 0
        min = 999999
        for list in result:
            for i in list:
                if i <= min:
                    min = i
            product += min
            # print(f'list{list} : min:{min} : product:{product}')
            min = 999999
        return product
这种方法在LeetCode用例上跑的时候超时了，没能跑过用例，可能是因为计算复杂度过高为O(n^2)，所以我又去官网上看了大神的写法。