目 录CONTENT

文章目录

LeetCode|907. 子数组的最小值之和

RobKing
2023-11-27 / 0 评论 / 2 点赞 / 181 阅读 / 1,185 字

LeetCode|907. 子数组的最小值之和

给定一个整数数组 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 * 104
1 <= arr[i] <= 3 * 104

暴力超时

func sumSubarrayMins(arr []int) int {
    const MOD = 1e9+7
    n := len(arr)
    res := 0
    for i := 0; i < n; i ++ {
        minv := arr[i]
        for j := i; j < n; j ++ {
            minv = min(minv, arr[j])
            res += minv
        }
    }
    return res % MOD
}

单调栈+贡献值

func sumSubarrayMins(arr []int) int {
    const Mod int = 1e9+7
    // 单调栈+贡献值
    // 如果知道 以 当前元素为最小值的 左右边界,然后知道这个区间内子数组的总数量,便可以知道当前值对结果的贡献
    // 以当前为最小值的左右边界 可以通过单调栈 (下/上一个更小的值)得出
    // 区间内的子数组数量,上一个更小的值到当前位置的元素数量left[i] * 当前到右边下一个更小的值的位置的元素数量right[i]
    // 贡献为 left[i]*right[i]*arr[i]
    n := len(arr)
    st := make([]int, 0)
    left, right := make([]int, n), make([]int, n)
    // 左边(下一个更小)
    for i := 0; i < n; i ++ {
        num := arr[i]
        for len(st) != 0 && num <= arr[st[len(st)-1]] {
            st = st[:len(st)-1]
        }
        if len(st) == 0 {
            left[i] = i + 1
        }else {
            left[i] = i - st[len(st)-1]
        }
        st = append(st, i)
    }
    st = []int{}
    // 右边(下一个更小)
    for i := n-1; i >= 0; i -- {
        num := arr[i] 
        for len(st) != 0 && num < arr[st[len(st)-1]] {
            st = st[:len(st)-1]
        }
        if len(st) == 0 {
            right[i] = n - i 
        } else {
            right[i] = st[len(st)-1] - i
        }
        st = append(st, i)
    }
    res := 0
    for i := 0; i < n; i ++ {
        res = ( res + arr[i] * left[i] * right[i] ) % Mod 
    }
    return res 
}

496. 下一个更大元素 I

nums1 中数字 x下一个更大元素 是指 xnums2 中对应位置 右侧第一个x 大的元素。

给你两个 没有重复元素 的数组 nums1nums2 ,下标从 0 开始计数,其中nums1nums2 的子集。

对于每个 0 <= i < nums1.length ,找出满足 nums1[i] == nums2[j] 的下标 j ,并且在 nums2 确定 nums2[j]下一个更大元素 。如果不存在下一个更大元素,那么本次查询的答案是 -1

返回一个长度为 nums1.length 的数组 ans 作为答案,满足 ans[i] 是如上所述的 下一个更大元素

示例 1:

输入:nums1 = [4,1,2], nums2 = [1,3,4,2].
输出:[-1,3,-1]
解释:nums1 中每个值的下一个更大元素如下所述:
- 4 ,用加粗斜体标识,nums2 = [1,3,4,2]。不存在下一个更大元素,所以答案是 -1 。
- 1 ,用加粗斜体标识,nums2 = [1,3,4,2]。下一个更大元素是 3 。
- 2 ,用加粗斜体标识,nums2 = [1,3,4,2]。不存在下一个更大元素,所以答案是 -1 。

示例 2:
输入:nums1 = [2,4], nums2 = [1,2,3,4].
输出:[3,-1]
解释:nums1 中每个值的下一个更大元素如下所述:
- 2 ,用加粗斜体标识,nums2 = [1,2,3,4]。下一个更大元素是 3 。
- 4 ,用加粗斜体标识,nums2 = [1,2,3,4]。不存在下一个更大元素,所以答案是 -1 。
 

提示:
1 <= nums1.length <= nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 104
nums1和nums2中所有整数 互不相同
nums1 中的所有整数同样出现在 nums2 中
func nextGreaterElement(nums1 []int, nums2 []int) []int {
    // 思路:单调栈,预处理num2元素,保存到map中
    // 单调栈:从后遍历,遍历过程如果出现大于的了,将栈中所有小于当前元素去掉,因为没意义了
    // map用来保存当前元素值的 后面最大的元素(下一个更大的元素),即是栈顶
    n1, n2 := len(nums1), len(nums2)
    mp := make(map[int]int)
    st := make([]int, 0)
    for i := n2-1; i >= 0; i -- {
        num := nums2[i]
        for len(st) != 0 && num > st[len(st)-1] {
            st = st[:len(st)-1]
        } 
        if len(st) == 0 {
            mp[num] = -1
        }else {
            mp[num] = st[len(st)-1]
        }
        st = append(st, num)
    }
    res := make([]int, 0)
    for i := 0; i < n1; i ++ {
        res = append(res, mp[nums1[i]])
    }
    return res 
}
2

评论区