力扣 907. 子数组的最小值之和

解法1: 贡献法

def sumSubarrayMins(arr):
    # 单调栈贡献法
    n = len(arr)
    left, right= [-1] * n, [n] * n
    stack = []
    for i in range(n):
        while stack and arr[stack[-1]] >= arr[i]:
            right[stack.pop()] = i
        stack.append(i)
    stack = []
    for i in range(n - 1 ,-1, -1):
        while stack and arr[stack[-1]] > arr[i]:
            left[stack.pop()] = i
        stack.append(i)
    ret = 0
    for i in range(n):
        ret += (i - left[i]) * (right[i] - i) * arr[i]
    return ret % (10 ** 9 + 7)