LeetCode907 子数组的最小值之和

发表于 | 分类于 |
字数统计: 546 | 阅读时长 ≈ 2

链接: https://leetcode.cn/problems/sum-of-subarray-minimums/

题意

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

解法

如果统计所有的子数组计算其最小值相加很显然会超时
所以考虑计算每个数的贡献
当前数a[i]在哪几个区间里是最小值，计算出区间的数量
将所有的区间数量相加就可以得到最后的结果

问题就转化为如何计算符合条件区间数量
只需要直到左边界l和右边届r
满足[l, r]的闭区间内a[i]是最小值
为了得到这个左右边界，可以通过找到左边小于a[i]的第一个数的位置，和右边小于等于a[i]的第一个数的位置
这个找的过程可以借助单调栈来进行
维护一个递增的单调栈 在出栈入栈的过程中完成找左右边界的过程
有一些细节可以具体看代码

注意不能两边都找严格小于
以数组 [1,3,1,2]为例，如果左右两侧都是找严格小于，那么第一个 1 和第二个 1 算出来的边界范围都是一样的
这道题可能没有影响 因为区间数量是一样的
但如果涉及到数组的其他的属性值就会出错

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
typedef long long ll;
class Solution {
public:
    int sumSubarrayMins(vector<int>& arr) {
        int n = arr.size(), mod = 1e9 + 7;
        ll ans = 0;
        vector<int> left(n, -1), right(n, n);
        // left[i] 为左侧严格小于 arr[i] 的最近元素位置（不存在时为 -1）
        // right[i] 为右侧小于等于 arr[i] 的最近元素位置（不存在时为 n）
        vector<int> stk;
        for (int i = 0; i < n; i++) {
            while(stk.size() && arr[stk.back()] >= arr[i]) {
                right[stk.back()] = i;
                stk.pop_back();
            }
            if (stk.size()) {
                left[i] = stk.back();
            }
            stk.push_back(i);
        }
        for (int i = 0; i < n; i++) {
            ll l = left[i] + 1, r = right[i] - 1; 
            ans += arr[i] * (r - i + 1) * (i - l + 1);
            // cout << ans << endl;
            ans %= mod;
        }
        return ans;
    }
};