Leetcode907 Sum Of Subarray Minimums

Posted on In

题目描述

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
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.

Note:

  • 1 <= A.length <= 30000
  • 1 <= A[i] <= 30000

    解析

    题意很好理解，求一个数组的所有子数组里最小元素的和，暴力法可以解出来，也就是遍历所有的子数组，时间复杂度为O(N^2)，不过这个题目还有个限制条件，A的长度会达到30000，根据做这类题目的经验，凡是长度过万，O（N^2）必然会超时。

的确，还有O（N）的思路。

方法一

这是我做这题的时候想出来的一个办法，也是Solution中的方法一。

取数组中某个元素i，如果区间(left, i], [i,right) 中所有元素都大于A[i]，则一共有(i - left) * (right - i)个子数组的最小值为A[i], 注意区间的开闭，即A[left] <= A[i], A[right] <= A[i]，有了这样一个intuition，我们则可以从左右两边遍历，对每个i，求出上一个小于等于A[i]的数字所在的位置，并保存起来。

这是一个先进后出的结构，可以用栈实现O(N)的求解left，right的算法，具体代码如下

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
public int sumSubarrayMins(int[] A) {
    // 取模
    int mod = 1000000007;
    int res = 0;
    // left[i]是左边上一个小于等于A[i]的元素的index
    int[] left = new int[A.length];
    // right[i]是上一个右边小于等于A[i]的元素的index
    int[] right = new int[A.length];
    Stack<Integer> st = new Stack<>();
    // 基数设为-1，即(-1, 0]区间
    st.push(-1);
    for(int i = 0; i < A.length; i++){
        // left数组构造，如果栈顶对应的元素小于A[i]，利用栈的性质，栈顶对应的元素为left[i]，因为再往左，min就不会为A[i]了， 下面right同理
        if(st.peek() == -1 || A[i] > A[st.peek()]){
            left[i] = st.peek();
            st.push(i);
        }
    
        else{
            while(st.peek() != -1 && A[st.peek()] >= A[i])
                st.pop();
            left[i] = st.peek();
            st.push(i);
        }
    }
    // 从右往左，再来一遍
    st.clear();
    st.push(A.length);
    for(int i = A.length - 1; i > - 1; i--){
        if(st.peek() == A.length || A[i] >= A[st.peek()]){
            right[i] = st.peek();
            st.push(i);
        }
        else{
            while(st.peek() != A.length && A[st.peek()] > A[i])
                st.pop();
            right[i] = st.peek();
            st.push(i);
        }
    }
    // 从0 到 N以每个元素为中心，向两边扩展，求子数组，所有子数组会全部覆盖
    for(int i = 0; i < A.length; i++){
        res = (res + (((i - left[i]) * (right[i] - i)) % mod) * A[i] % mod) % mod;
    }
    return res;
}

不过还有个方法二，今晚时间有限，待来日总结