Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment