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

ACK

发布于 2020-01-14 18:06:06

1.4K0

发布于 2020-01-14 18:06:06

文章被收录于专栏：flytam之深入前端技术栈

leetcode907 子数组的最小值之和

一道涉及到单调栈的应用的题目

题目如下

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

思路分析：这里是求出子数组的最小值之和，其实并不需要知道这个子数组的除了最大值之外其它数值。通过对实例的分析，我们可以得出一个17运用公式如何算出来：(1+0-0 (0-0)*(0-0))*3+(3-0+1+(3-1)*(1-0))*1+(1+3-2+(3-2)*(2-2))*2+(1+3-3+(3-3)*(3-3))*4 = 17。

也就是说，遍历数组的每一个值，找出以该数组为最小值的组合次数，乘积求和为和即可。假设当前数字下标为a，该数字往前的第一个小于该数的下标为x（也就是最小数组最大边界）、往后第一个小于等于该数的下标为y，那么次数就是y-x+1+(y-a)*(y-b)。例如以[3,1,2,4]的2为例子，则a=2 x=2 y=3，所以次数3-2+1+(3-2)*(2-2) = 2

所以这个题目就变成了，找出对于数组中每一个值，它的前继小于自己的下标/后继小于等于自己的下标。那么如何寻找呢。

解法 1: 常规解法。就是遍历数组，每个数字往前往后继续找边界。这样时间复杂度为o(n)。在第 87 个 case 就超时了。

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)
}

解法 2:稍微优化的版本，记录前一次的边界值，当前值小于前面值，直接从前面的边界开始找。到第 100 个测试样例还是没通过。仔细观察，其实优化版本只对部分 case 简化，其实它还是o(n2)的时间复杂度。要通过这里肯定不能o(n2)。

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)
}

解法 3: 使用单调栈找出每一个数的边界。只需要o(n)的时间复杂度就可以找出来（因为每个元素只会进/出栈一次）

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
}