LC 907 Sum of Subarray Minimums

Decrisption

Given an array of integers arr, find the sum of min(b), where b ranges over every (contiguous) subarray of arr. Since the answer may be large, return the answer modulo \(10^9\) + 7.

Input

Example 1:

Input: \(arr = [3,1,2,4]\)
Output: 17
Explanation:
Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4].
Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1.
Sum is 17.
Example 2:

Input: \(arr = [11,81,94,43,3]\)
Output: 444

Constraints

1\(\leq\)arr.length$\leq$3\(10^4\)
1\(\leq\)arr[i]$\leq$3\(10^4\)

Solution

思路：
方法一：暴力计算
直接计算每一个子数组中的最小值并全部相加，时间复杂度为\(O\)(\(n^2\))，显然会超时。

class Solution {
public:
    int MOD=1e9+7;
    int sumSubarrayMins(vector<int>& arr) {
        int n=arr.size();
        int ans=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<=i;j++){
                int min=*min_element(arr.begin()+j,arr.begin()+i+1);
                ans+=min;
                ans%=MOD;
            }
        }
        return ans;
    }
};

方法二：两次单调栈+贡献法
方法一中由于重复计算了许多次相同的最小值，所以我们要想办法免去复杂计算。对于数组中的每一个元素，其都会在最终的答案中有一个贡献值。该贡献值可以看成是每一个元素作为子数组的最小元素的次数。

注意到：对于某一个元素\(x\)，假定其下标为\(i\)，如果x是某一个子数组的最小值，该子数组的左端点为\(left\)，右端点为\(right\)，那么在[\(left\),\(right\)]范围内所有包含\(x\)的子数组的最小值都为x，x的贡献为\(arr[i]\)\(*\)(\(i-left\))\(*\)(\(right-i\))。所以我们要找到每一个元素左侧第一个小于该元素的位置\(left\)和右侧第一个小于该元素的位置\(right\)。这样在区间\((left,right)\)范围内包含\(x\)的子数组的最小值可以确定为x，x的贡献值为\(arr[i]*(i-left)*(right-i)\).

class Solution {
public:
    int MOD=1e9+7;
    typedef long long ll;
    int sumSubarrayMins(vector<int>& arr) {
        int n=arr.size();
        ll ans=0;
        vector<ll> left(n,-1);    //左边界为-1
        vector<ll> right(n,n);   //右边界为n
        stack<ll> stk;
        for(int i=0;i<n;i++){
            while(!stk.empty()&&arr[stk.top()]>arr[i]){
                stk.pop();
            }
            if(!stk.empty()){
                left[i]=stk.top();
            }
            stk.push(i);
        }

        while(!stk.empty()) stk.pop();

        for(int i=n-1;i>=0;i--){
            while(!stk.empty()&&arr[stk.top()]>=arr[i]){
                stk.pop();
            }
            if(!stk.empty()){
                right[i]=stk.top();
            }
            stk.push(i);
        }

        for(ll i=0;i<n;i++){
            ans+= (ll)arr[i]*(i-left[i])*(right[i]-i);
            ans%=MOD;
        }
        return ans;
    }
};

时间复杂度:\(O(n)\)
空间复杂度:\(O(n)\)