每日一题｜2022-10-28｜907. 子数组的最小值之和｜今天不想学，后面补上

907. 子数组的最小值之和

// c+v，今天不想学
func sumSubarrayMins(arr []int) (ans int) {
    const mod int = 1e9 + 7
    n := len(arr)
    left := make([]int, n)
    right := make([]int, n)
    monoStack := []int{}
    for i, x := range arr {
        for len(monoStack) > 0 && x <= arr[monoStack[len(monoStack)-1]] {
            monoStack = monoStack[:len(monoStack)-1]
        }
        if len(monoStack) == 0 {
            left[i] = i + 1
        } else {
            left[i] = i - monoStack[len(monoStack)-1]
        }
        monoStack = append(monoStack, i)
    }
    monoStack = []int{}
    for i := n - 1; i >= 0; i-- {
        for len(monoStack) > 0 && arr[i] < arr[monoStack[len(monoStack)-1]] {
            monoStack = monoStack[:len(monoStack)-1]
        }
        if len(monoStack) == 0 {
            right[i] = n - i
        } else {
            right[i] = monoStack[len(monoStack)-1] - i
        }
        monoStack = append(monoStack, i)
    }
    for i, x := range arr {
        ans = (ans + left[i]*right[i]*x) % mod
    }
    return
}