Leetcode 2024-11-27 题目分享

Leetcode

907. 子数组的最小值之和

给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。

由于答案可能很大，因此 返回答案模 10^9 + 7 。

示例 1：
1
2
3
4
5
输入：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：
1
2
输入：arr = [11,81,94,43,3]
输出：444
提示：

1 <= arr.length <= 3 * 10^4

1 <= arr[i] <= 3 * 10^4

思路

明显贡献法求解。

对于遍历到的第i个数，他有a[i：i]，a[i-1：i]…a[1：i] 总共i个连续子数组。

找到第一个a[j]<a[i]的分割点：

对于所有a[1：k]，k<=j的子数组，它的最小值肯定都是a[1：k]中的最小值。
对于所有a[k：i]，k>j的子数组，它的最小值肯定都是a[i]。

所以维护每个位置上的连续子数组最小值的和dp[i]：

dp[i] = dp[j]+arr[i]*(i-j)

为了快速找到最小值，使用树状数组。

代码

class Solution {
public:
    int sumSubarrayMins(vector<int>& arr) {
        int n = arr.size(), N = 3e4+10;
        typedef long long ll;
        vector<int> tr(N, 0);
        function<void(int, int)> upd = [&](int idx, int val){
            for (int i = idx;i < N;i += i&-i) tr[i] = max(tr[i], val);
        };
        function<int(int)> qry = [&](int idx){
            int ans = 0;
            for (int i = idx;i > 0;i -= i&-i) ans = max(ans, tr[i]);
            return ans;
        };
        ll M = 1e9+7, res = 0;
        vector<ll> ans(n+1, 0);
        for (int i = 1;i <= n;i++){
            int pre = qry(arr[i-1]-1);
            ans[i] = (ans[pre]+arr[i-1]*(i-pre))%M;
            res = (res+ans[i])%M;
            upd(arr[i-1], i);
        }
        return (int)res;
    }
};

复杂度分析

时间复杂度: O(nlogn) 。
空间复杂度: O(n) 。