907. Sum of Subarray Minimums.md

907. Sum of Subarray Minimums

https://leetcode.com/problems/sum-of-subarray-minimums/

solution

• 单调栈

class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        n = len(arr)
        left = [-1] * n
        right = [n] * n
        stack = []

        for i, value in enumerate(arr):
            while stack and arr[stack[-1]] >= value:
                stack.pop()
            if stack:
                left[i] = stack[-1]
            stack.append(i)

        stack = []

        for i in range(n - 1, -1, -1):
            while stack and arr[stack[-1]] > arr[i]:
                stack.pop()
            if stack:
                right[i] = stack[-1]
            stack.append(i)

        mod = 10**9 + 7
        result = sum((i - left[i]) * (right[i] - i) * value for i, value in enumerate(arr)) % mod
        return result

时间复杂度：O()
空间复杂度：O()

• 暴力解法超时

class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        res_list = []
        for i in range(len(arr)):
            for j in range(i+1, len(arr)+1):  # 注意边界
                res_list.append(min(arr[i:j]))

        mod = 10**9 + 7
        return sum(res_list) % mod