【每日一题】子数组的最小值之和

文章目录

Tag
题目来源
题目解读
解题思路
- 方法一：贡献法+单调栈
写在最后

Tag

【贡献法】【单调栈】【数组】【2023-11-27】

题目来源

907. 子数组的最小值之和

题目解读

计算整数数组的连续子数组中最小值的和。

解题思路

本题朴素的解决思想是求出所有的连续子数组，遍历每一个子数组然后将每一个子数组的最小和加和得到结果，但是该方法时间复杂度过高。现在介绍一种时间复杂度较优的方法——贡献法。

方法一：贡献法+单调栈

我们从数组中的每一个元素作为连续子数组中的最小值这一角度考虑，比如在数组 arr = [3, 1, 2, 4] 中，考虑 1 作为子数组中的最小值的情况，有这些子数组满足 1 是子数组中的最小值 :
$[3, 1], [3, 1, 2], [3, 1, 2, 4], [1], [1, 2], [1, 2, 4]$
共计6个。利用乘法原理有：
$6 = (i - a) * (b - i) = 2 * 3$
其中，a 表示在 arr 数组中 1 左侧比 1 小的第一个元素的下标，默认值为 -1，此时 a = -1；
b 表示在 arr 数组中 1 右侧比 1 小的第一个元素的下标，默认值为 n，此时 b = n。

以上是 arr 数组中无重复元素的情况，我们只需要找出元素 arr[i] 左侧第一个比它小的元素下标 a、元素 arr[i] 右侧第一个比它小的元素下标 b，利用乘法原理即可得到 arr[i] 作为连续子数组的最小值时的答案，我们遍历数组中的所有元素，计算作为连续子数组的最小值时的答案，将所有答案进行加和得到最终的答案，时间复杂度为 $O (n)$ 。

一般的情况，若是 arr 数组中有重复元素出现会怎么样呢？此处参考贡献法+单调栈+三种实现版本（附题单）Python/Java/C++/Go。

如果 arr 有重复元素，例如 arr=[1, 2, 4, 2, 3, 1]，其中第一个 2 和第二个 2 对应的边界都是开区间 (0,5)，子数组 [2, 4, 2, 3] 都包含这两个 2，这样在计算答案时就会重复统计同一个子数组，算出错误的结果。

为避免重复统计，可以修改边界的定义，把右边界改为「找小于或等于 arr[i] 的数的下标」，那么：

第一个 2 对应的边界是 (0,3)，子数组需要在 (0,3) 范围内且包含下标 1；
第二个 2 对应的边界是 (0,5)，子数组需要在 (0,5) 范围内且包含下标 3。
这样以第一个 2 为最小值的子数组，就不会「越界」包含第二个 2 了，从而解决了重复统计子数组的问题。

实现代码

#define MOD 1000000007
class Solution {
public:
    int sumSubarrayMins(vector<int>& arr) {
        int n = arr.size();
        vector<int> lLessIdx(n, -1);
        vector<int> rLessAndEquIdx(n, n);

        // 用单调栈更新 lLessIdx
        int i;
        stack<int> stk;
        // [3, 1, 2, 4]
        for(i = 0; i < n; ++i) {
            while(!stk.empty() && arr[stk.top()] >= arr[i]) {
                stk.pop();
            }
            if (!stk.empty()) lLessIdx[i] = stk.top();
            stk.push(i);
        }   

        // 用单调栈更新 rLessAndEquIdx
        while (!stk.empty()) stk.pop();
        for(i = n-1; i >= 0; --i) {
            while(!stk.empty() && arr[stk.top()] > arr[i]) {
                stk.pop();
            }
            if (!stk.empty()) rLessAndEquIdx[i] = stk.top();
            stk.push(i);
        }

        long ans = 0;
        for(i = 0; i < n; ++i) {
            int a = lLessIdx[i], b = rLessAndEquIdx[i];
            ans += (long)((i - a) * (b - i)) % MOD * arr[i] % MOD; // 乘法原理
            ans %= MOD;
        }
        return (int)ans;
    }
};