leetcode 907子数组的最小值之和题解

给定一个整数数组 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

func sumSubarrayMins(A []int) int {
	sum := 0
	length := len(A)
	for i, v := range A {
		tmpLeft, tmpRight := i, i
		for {
			// 都 到达边界或者找到第一个小于等于的
			if tmpLeft-1 >= 0 && A[tmpLeft-1] > v {
				tmpLeft--
			}

			if tmpRight+1 < length && A[tmpRight+1] >= v {
				tmpRight++
			}

			if (tmpLeft-1 < 0 || A[tmpLeft-1] <= v) && (tmpRight+1 == length || A[tmpRight+1] < v) {
				fmt.Println(tmpLeft, tmpRight)
				sum = sum + (i-tmpLeft+tmpRight-i+(tmpRight-i)*(i-tmpLeft)+1)*v
				break
			}
		}
	}
	return sum % int(math.Pow(10, 9)+7)
}

func sumSubarrayMins(A []int) int {
	// 记录前一个的左右边界
	pre := [2]int{}
	sum := 0
	length := len(A)
	var tmpLeft, tmpRight int
	for i, v := range A {
		if i > 0 && v <= A[i-1] {
			if v < A[i-1] {
				// 小于q前面的，左右用前面的
				tmpLeft, tmpRight = pre[0], pre[1]
			} else {
				// 等于，左用自己
				tmpLeft, tmpRight = i, pre[1]
			}

		} else {
			tmpLeft, tmpRight = i, i
		}

		for {
			if tmpLeft-1 >= 0 && A[tmpLeft-1] > v {
				tmpLeft--
			}
			if tmpRight+1 < length && A[tmpRight+1] >= v {
				tmpRight++
			}
			if (tmpLeft-1 < 0 || A[tmpLeft-1] <= v) && (tmpRight+1 == length || A[tmpRight+1] < v) {

				sum = sum + (i-tmpLeft+tmpRight-i+(tmpRight-i)*(i-tmpLeft)+1)*v
				pre[0] = tmpLeft
				pre[1] = tmpRight

				break
			}

		}
	}

	return sum % int(math.Pow(10, 9)+7)
}

type Item struct {
	low  int
	high int
}

func sumSubarrayMins(A []int) int {
	sum := 0
	length := len(A)
	if length == 1 {
		return A[0]
    }
    // lower  每个元素往左查找
    // higher 每个元素往右查找
	lower := []int{length - 1}

	higher := []int{0}

	store := make([]Item, len(A))

	for i := 1; i < length; i++ {

		highIndex := i
		lowIndex := length - i - 1

		// 当前元素小于等于栈顶元素。栈顶元素出栈。
		for len(higher) >= 1 && A[highIndex] <= A[higher[len(higher)-1]] {
			// 存储下标
			store[higher[len(higher)-1]].high = highIndex - 1
			// 出栈
			higher = higher[:len(higher)-1]
		}
		higher = append(higher, highIndex)

		// 当前元素小于栈顶元素。栈顶元素出栈。
		for len(lower) >= 1 && A[lowIndex] < A[lower[len(lower)-1]] {
			store[lower[len(lower)-1]].low = lowIndex + 1 // lower[len(lower)-1]
			lower = lower[:len(lower)-1]
		}

		// 当前index值入栈
		lower = append(lower, lowIndex)

	}

	// 还在栈内的元素说明边界
	for _, v := range higher {
		store[v].high = length - 1
	}

	for _, v := range lower {
		store[v].low = 0
	}

	for i, v := range store {
		sum = sum + (1+i-v.low+v.high-i+(v.high-i)*(i-v.low))*A[i]
	}
	return sum % 1000000007
}