907. Sum of Subarray Minimums

发表于 | 分类于 | 浏览 次

Given an array of integers A, find the sum of min(B), where B ranges over every (contiguous) subarray of A.

Since the answer may be large, return the answer modulo 10^9 + 7.

Example 1:

1
2
3
4
Input: [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.

解法1

统计以a[j]为right-most最小值的子数组的个数, 记作s[j].这样, 结果就是sum(s[j] * a[j]). 必须以right-most为条件,因为只有如此,才能把子数组分为不重合的集合以免重复计算.
问题于是转化为, 求最小的i(i<=j), a[i] , a[i+1] , …., a[j]都是大于等于a[j]的.以及最大的k(k>=j) , a[j+1], a[j+2],….,a[k]都大于a[j].然后问题可以进一步转化为找出位置j左边距离j位置最近且值比arr[j]小的位置，同时找出位置j右边距离j位置最近且值小于等于arr[j]的位置．

那么，假设位置j左边距离位置j最近且值比arr[j]小的位置为i，且位置j右边距离位置j最近且值小于等于arr[j]的位置为k，那么位置j左边有(i-1)-(k+1) + 1=i-k-1个元素大于等于arr[j]，同时，位置j右边有(k-1)-(i+1)-1 = k - i + 1个元素比arr[j]大．那么，以arr[j]为right-most最小值的子数组个数有(i-k) * (k-j)个．

对于一个数组[5,3,4,6]来说,包含3的子数组有6个.
这是因为3的左边有一个数, 右边有2个数.3可以在它的左边选择0个或者1个数, 在右边选择0或1个或2个构成子数组.因为包括3的子数组个数共有6个,分别是:
即包括3的子数组的个数是(j - i - 1) * (k - j - 1), 设j=1表示3的索引, i=-1，k = 4.

1
[[3],[5,3],[3,4],[3,4,6], [5,3,4],[5,3,4,6]]

过程

设a = [3,2,2,4].则对于第一个2来说，以它为right-most最小值的子数组有：[[2],[3,2]]，以第二个2为right-most最小值的子数组有：[[2],[2,2],[2,4],[3,2,2],[2,2,4],[3,2,2,4]]，共6个，因为在第二个2之前有两个数[3,2]都大于等于它，而在它之后有一个数小于等于它，则以第二个2为right-most最小值的子数组共有(2+1) * (1+1) = 6个．
然后使用单调栈来求数组a中a[j]左边第一个小于a[j]的元素a[i]和右边第一个小于等于a[j]的元素a[k].

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/***
 * 找出nums中元素nums[j]左边第一个小于nums[j]的元素nums[i],
 * 及nums[j]右边第一个小于等于nums[j]的元素nums[k]
 * @param nums
 */
vector<vector<int>> singleStack(vector<int> &nums) {
    stack<int> st;
    if (nums.size() < 1) {
        return {};
    }
    vector<vector<int>> res(nums.size(), vector<int>(2, -1));
    for (int i = 0; i < nums.size(); ++i) {
        while (!st.empty() && nums[st.top()] >= nums[i]) {
            int index = st.top();
            st.pop();
            int l = st.empty() ? -1 : st.top();
            int r = i;
            res[index][0] = l;
            res[index][1] = r;
        }
        st.push(i);
    }

    // 下面这些元素右边没有元素比它们小
    while (!st.empty()) {
        int index = st.top();
        st.pop();
        int l = st.empty() ? -1 : st.top();
        int r = nums.size();
        res[index][0] = l;
        res[index][1] = r;
    }
    return res;
}

void testsingleStack() {
//    vector<int> nums{2, 3, 2, 3, 5, 2, 3, 3};
    vector<int> nums{3, 1, 2, 4};
    vector<vector<int>> res = singleStack(nums);
    int total = 0;
    for (int i = 0; i < nums.size(); ++i) {
        cout << "nums[" << i << "] " << nums[i] << ":  " << res[i][0] << "," << res[i][1] << endl;

        // (i - res[i][0]) * (res[i][1] - i) 表示以nums[i]为最小值的子数组个数
        total += (i - res[i][0]) * (res[i][1] - i) * nums[i];
    }
    cout << total << endl;
}

AC代码

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
class Solution {
public:
    int sumSubarrayMins(vector<int>& A) {
        int cnt = 0;
        const int MOD = 1000000007;
        stack<int> s1;
        for(int i=0;i<A.size();++i){
            int r = i;
            while(!s1.empty() && A[s1.top()] >= A[i]){
                int idx = s1.top();
                s1.pop();
                int l = s1.empty() ? -1 : s1.top();
                cnt = (cnt + (r - idx) * (idx - l) * A[idx]) % MOD;
            }
            s1.push(i);
        }
        int r = A.size();
        while(!s1.empty()){
            int idx = s1.top();
            s1.pop();
            int l = s1.empty() ? -1 : s1.top();
            cnt = (cnt + (idx - l) * (r - idx) * A[idx]) % MOD;
        }
        return cnt;
    }
};

类似题

题目链接