当前位置：首页 > article >正文

力扣(LeetCode)907. 子数组的最小值之和(C++)

article 2024/9/20 12:10:10

枚举

请对题目有疑惑的小伙伴看枚举思想，有助于掌握最基本的解题思路。对于本题数据范围，枚举算法会超时。

请看题目描述：给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。
根据示例1：arr = [3,1,2,4]
连续子数组有10个： [3]，[1]，[2]，[4]，[3,1]，[1,2]，[2,4]，[3,1,2]，[1,2,4]，[3,1,2,4]
解题关键：找到10个子数组各自的最小值 3，1，2，4，1，1，2，1，1，1，求和即为示例1的答案。

最简单的做法，二重循环：外层遍历 arr，遍历的位置 i，内层遍历，从 i 向右枚举终点 j (以 i 为起点，长度递增的连续子数组)，答案就是求和 [i, j] 区间的最小值minnum

class Solution {
private:
    const int mod = 1e9 + 7;
public:
    int sumSubarrayMins(vector<int>& arr) {
        long long ans = 0;
        for (int i = 0; i < arr.size(); i ++) {
            int minnum = INT_MAX;
            for (int j = i; j < arr.size(); j ++) {
                if (arr[j] < minnum) minnum = arr[j];
                ans = (ans + minnum) % mod;
            }
        }
        return ans;
    }
};

时间复杂度 $O(n^2)$ ：二重循环的时间复杂度 $O(n^2)$ ，本题数据范围会TLE。
空间复杂度 $O (1)$ ：只使用常数级空间。

单调栈

在枚举算法中，先确定了左边界，枚举右边界，维护区间的最小值。因此时间复杂度是 $O(n^2)$ 。反过来想，是不是可以枚举数组的每个数，确定以枚举数值为最小值的区间左右边界就好？结论是可以的：单调栈思想。

设枚举位置i，arr[i]的左边界就是从i往左遍历，第一次出现小于arr[i]的数组元素，左边界的位置记为left[i]；arr[i]的右边界同理，右边界的位置记为right[i]。对于枚举元素，[左边界, 枚举元素]区间的数，都大于枚举元素本身，提示我们单调栈维护左边界和枚举元素，则下次枚举时找左边界时，只需考虑栈内元素。如对原理有疑惑请评论区提问。

得出计算公式，以arr[i]为最小值的连续区间数： $((i-1)-left[i]+1)\times(right[i]-(i+1)+1)=(i-left[i])\times(right[i]-i)$

arr[i]对答案的贡献： $(i-left[i])\times(right[i]-i)\times arr[i]$

同理计算右边界，反向枚举一遍。

注意：

右边界稍有特别：设枚举位置i，往i右遍历，arr[i]右侧第一次出现小于等于arr[i]的数组元素。这是为了避免重复统计。
设左边界-1表示枚举位置i左侧所有元素小于枚举元素arr[i]。
关键变量：单调栈S，数组left和right。

代码如下，有疑惑请评论区提问。

class Solution {
private:
    const int mod = 1e9 + 7;
    stack<int> S;
public:
    int sumSubarrayMins(vector<int>& arr) {
        long long ans = 0;
        vector<int> left(arr.size()), right(arr.size());
        for (int i = 0; i < arr.size(); i ++) {
            while (S.size() && arr[S.top()] >= arr[i]) S.pop();
            if (S.empty()) left[i] = -1;
            else left[i] = S.top();
            S.push(i);
        }
        S = {};
        for (int i = arr.size() - 1; i >= 0; i --) {
            while (S.size() && arr[S.top()] > arr[i]) S.pop();
            if (S.empty()) right[i] = arr.size();
            else right[i] = S.top();
            S.push(i);
        }
        for(int i = 0; i < arr.size(); i ++) {
            ans = (ans + (long long)(i - left[i]) * (right[i] - i) * arr[i]) % mod;
        }
        return ans;
    }
};