【2022-10-28每日一题】907. 子数组的最小值之和[Medium]
2022-10-28
3分钟阅读时长
2022-10-28每日一题：907. 子数组的最小值之和
难度：Medium
标签：栈 、 数组 、 动态规划 、 单调栈
给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。
由于答案可能很大，因此 返回答案模 10^9 + 7 。
示例 1：
输入：arr = [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。
示例 2：
输入：arr = [11,81,94,43,3] 输出：444
提示：
1 <= arr.length <= 3 * 1041 <= arr[i] <= 3 * 104
方法一：单调栈
官方优化版
const mod int = 1e9+7
func sumSubarrayMins(arr []int) int {
n := len(arr)
left, right := make([]int, n), make([]int, n)
stack := []int{-1} // -1 为哨兵
for i := 0; i < n; i++ {
for len(stack) > 1 && arr[stack[len(stack)-1]] >= arr[i] {
stack = stack[:len(stack)-1]
}
left[i] = i - stack[len(stack)-1]
stack = append(stack, i)
}
stack = []int{n}
for i := n - 1; i >= 0; i-- {
for len(stack) > 1 && arr[stack[len(stack)-1]] > arr[i] {
stack = stack[:len(stack)-1]
}
right[i] = stack[len(stack)-1] - i
stack = append(stack, i)
}
ans := 0
for i, x := range arr {
ans = (ans + x * left[i] * right[i]) % mod
}
return ans
}
延迟计算宽度
const mod int = 1e9+7
func sumSubarrayMins(arr []int) int {
n := len(arr)
left, right := make([]int, n), make([]int, n)
stack := []int{-1} // -1 为哨兵
for i := 0; i < n; i++ {
for len(stack) > 1 && arr[stack[len(stack)-1]] >= arr[i] {
stack = stack[:len(stack)-1]
}
left[i] = stack[len(stack)-1]
stack = append(stack, i)
}
stack = []int{n}
for i := n - 1; i >= 0; i-- {
for len(stack) > 1 && arr[stack[len(stack)-1]] > arr[i] {
stack = stack[:len(stack)-1]
}
right[i] = stack[len(stack)-1]
stack = append(stack, i)
}
ans := 0
for i, x := range arr {
ans = (ans + x * (i - left[i]) * (right[i]-i)) % mod
}
return ans
}
二次遍历变形
func sumSubarrayMins(arr []int) (ans int) {
n := len(arr)
left := make([]int, n)
right := make([]int, n)
for i := range right {
right[i] = n
}
st := []int{-1} // -1 为哨兵，方便计算赋值
for i, x := range arr {
for len(st) > 1 && arr[st[len(st)-1]] >= x {
right[st[len(st)-1]] = i // i 恰好是栈顶的右边界
st = st[:len(st)-1]
}
left[i] = st[len(st)-1] // 可以直接计算 i - st[len(st)-1]
st = append(st, i)
}
for i, x := range arr {
ans += x * (i - left[i]) * (right[i] - i) // 累加贡献
}
return ans % (1e9 + 7)
}
优化版本：一次遍历
func sumSubarrayMins(arr []int) (ans int) {
arr = append(arr, -1)
st := []int{-1} // 哨兵
for r, x := range arr {
for len(st) > 1 && arr[st[len(st)-1]] >= x {
i := st[len(st)-1]
st = st[:len(st)-1]
ans += arr[i] * (i - st[len(st)-1]) * (r - i) // 累加贡献
}
st = append(st, r)
}
return ans % (1e9 + 7)
}
复杂度分析
- 时间复杂度：O(n)。
- 空间复杂度：O(n)。
方法二：动态规划
const mod int = 1e9 + 7
func sumSubarrayMins(arr []int) (ans int) {
n := len(arr)
dp := make([]int, n)
stack := []int{} // 栈中保持数组索引
for i, x := range arr {
// 移除栈顶比当前数大的所有数
for len(stack) > 0 && arr[stack[len(stack)-1]] > x {
stack = stack[:len(stack)-1]
}
k := i + 1 // 栈为空的k值
if len(stack) > 0 {
k = i - stack[len(stack)-1]
}
dp[i] = k * x
if len(stack) > 0 {
dp[i] += dp[i-k]
}
ans = (ans+dp[i]) % mod
stack = append(stack, i)
}
return ans
}
复杂度分析
- 时间复杂度：O(n)。
- 空间复杂度：O(n)。