題目

給定一個整數陣列 A，找到 min(B) 的總和，其中 B 的範圍為 A 的每個（連續）子陣列。

由於答案可能很大，因此返回答案模 10^9 + 7。

示例：輸入：[3,1,2,4] 輸出：17

解釋：子陣列為 [3]，[1]，[2]，[4]，[3,1]，[1,2]，[2,4]，[3,1,2]，[1,2,4]，[3,1,2,4]。

最小值為 3，1，2，4，1，1，2，1，1，1，和為 17。

提示：1 <= A <= 30000

1 <= A[i] <= 30000

1、單調棧；時間複雜度O(n)，空間複雜度O(n)

func sumSubarrayMins(arr []int) int {	res := 0	stack := make([]int, 0) // 遞增棧	stack = append(stack, -1)	total := 0	for i := 0; i < len(arr); i++ {		for len(stack) > 1 && arr[i] < arr[stack[len(stack)-1]] { // 小於棧頂			prev := stack[len(stack)-1]			stack = stack[:len(stack)-1]			total = total - arr[prev]*(prev-stack[len(stack)-1])		}		stack = append(stack, i)		total = total + arr[i]*(i-stack[len(stack)-2])		res = (res + total) % 1000000007	}	return res % 1000000007}

2、單調棧；時間複雜度O(n)，空間複雜度O(n)

func sumSubarrayMins(arr []int) int {	res := 0	stack := make([][2]int, 0) // 遞增棧	sum := 0	for i := 0; i < len(arr); i++ {		count := 1		for len(stack) > 0 && arr[i] < stack[len(stack)-1][0] { // 小於棧頂			prev := stack[len(stack)-1]			stack = stack[:len(stack)-1]			sum = sum - prev[0]*prev[1]			count = count + prev[1]		}		stack = append(stack, [2]int{arr[i], count})		sum = sum + arr[i]*count		res = (res + sum) % 1000000007	}	return res % 1000000007}

3、中心擴充套件；時間複雜度O(n^2)，空間複雜度O(1)

func sumSubarrayMins(arr []int) int {	res := 0	for i := 0; i < len(arr); i++ {		left, right := i-1, i+1		for ; left >= 0; left-- {			if arr[left] < arr[i] {				break			}		}		for ; right < len(arr); right++ {			if arr[right] <= arr[i] { // 注意邊界				break			}		}		sum := arr[i] * (i - left) * (right - i)		res = (res + sum) % 1000000007	}	return res % 1000000007}

Medium題目，使用單調棧