sumSubarray.go

const breakpoint = int(1e9+7)

func popStack(i int, arr []int, result int, stack []int) (int, []int) {
    end := len(stack)-1
    prevMinIndex := stack[end]
    stack[end] = 0
    stack = stack[:end]

    nextPrevIndex := -1
    if len(stack) > 0 {
        nextPrevIndex = stack[end-1]
    }
    delta := arr[prevMinIndex] * (i - prevMinIndex) * (prevMinIndex - nextPrevIndex)
    
    result = (result + delta) % breakpoint
    return result, stack
}
func sumSubarrayMins(arr []int) int {
    if len(arr) == 0 {
        return 0
    }
    
    stack := []int{}
    result := 0
    for i, v := range arr {
        for len(stack) > 0 && v < arr[stack[len(stack)-1]] {
            result, stack = popStack(i, arr, result, stack)
            // fmt.Println(result, stack)
        }
        stack = append(stack, i)
    }
    for len(stack) > 0 {
        result, stack = popStack(len(arr), arr, result, stack)
        // fmt.Println(result, stack)
    }
    
    return result
}