題目
給定一個整數陣列 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題目,使用單調棧
最新評論