leetcode 907子数组的最小值之和题解
- 2020 年 1 月 14 日
- 筆記
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 }
