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