907. 子数组的最小值之和

907. 子数组的最小值之和

• 难度: medium
• 原始链接: https://leetcode.cn/problems/sum-of-subarray-minimums
• 标签: 单调栈

解法一: 单调栈

go

func sumSubarrayMins(arr []int) int {
    n := len(arr)
    leftArr := make([]int, n)
    queue := []int{}
    for i, num := range arr {
        for len(queue) > 0 && arr[queue[len(queue) - 1]] > num {
            queue = queue[:len(queue) - 1]
        }
        if len(queue) == 0 {
            leftArr[i] = -1
        } else {
            leftArr[i] = queue[len(queue) - 1]
        }
        queue = append(queue, i)
    }
    rightArr := make([]int, n)
    queue = []int{}
    for i := n - 1; i >= 0; i-- {
        num := arr[i]
        for len(queue) > 0 && arr[queue[len(queue) - 1]] >= num {
            queue = queue[:len(queue) - 1]
        }
        if len(queue) == 0 {
            rightArr[i] = n
        } else {
            rightArr[i] = queue[len(queue) - 1]
        }
        queue = append(queue, i)
    }
    ans := 0
    const MOD = 1000000007
    for i, num := range arr {
        ans = (ans + num * (i - leftArr[i]) * (rightArr[i] - i)) % MOD
    }
    return ans
}