题目描述

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.

Note:

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

样例

Example 1:

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

单调栈 $O(n)$

https://medium.com/@ChYuan/leetcode-907-sum-of-subarray-minimums-%E5%BF%83%E5%BE%97-medium-bd342e1f1a9d

For example:
[3, 7, 8, 4, 2]
There is no previous less element for 3.
The previous less element of 7 is 3.
The previous less element of 8 is 7.
The previous less element of 4 is 3.
There is no previous less element for 2.
什麼是 the next less element?
從目前的數字(at indexK) 往後找，第一個遇到比 indexK 小的值。
What is the next less element of an element?
For example:
[3, 7, 8, 4, 2]
There is no next less element for 2.
The next less element of 4 is 2.
The next less element of 8 is 4.
The next less element of 7 is 4.
The next less element of 8 is 2.
之後 previous less element 簡稱 PLE， next less element 簡稱 NLE。

[2, 9, 7, 8, 3, 4, 6, 1]
 |                    |

the previous less the next less
element of 3 element of 3

After finding both NLE and PLE of 3, we can determine the
distance between 3 and 2(previous less) , and the distance between 3 and 1(next less).
In this example, the distance is 4 and 3 respectively.
How much the element 3 contributes to the final answer?
It is 3(43).
What is the final answer?
Denote by left[i] the distance between element A[i] and its PLE.
Denote by right[i] the distance between element A[i] and its NLE.
The final answer is,
sum(A[i]left[i]right[i] )

這樣想會有個問題，就是其中的 4 種情形和 3 種情形看起來都會包含 3，合起來的 subArray 不就會有兩個 3?
其實其中一邊的 3 應該是要空集合! 因為所有的 subarray 都要包含 3，所以一邊都包含 3，另一邊就把 3 當成空集合，這樣組合起來就恰恰好一個 3，也就是應該是這樣的:
[9, 7, 8, 3] -> [ ], [8, 3], [7, 8, 3], [9, 7, 8, 3]
[3, 4, 6] -> [3], [3, 4], [3, 4, 6]
這樣就可以完美組合成 12 種情形! 所以簡化後，就是left[i]right[i]。
這些 subarray 的最小值都是 3，所以包含 element 3 的所有 contiguous subArray 的最小值總和就是 (43)3。
對於任一個 element 的一般化公式: left[i]right[i]*A[i]

时间复杂度 O(n)

参考文献

Java 代码

public int sumSubarrayMins(int[] A) {
        int res = 0, n = A.length, mod = (int)1e9 + 7;
        int[] left = new int[n], right = new int[n];
        Stack<int[]> s1 = new Stack<>(), s2 = new Stack<>();
        for (int i = 0; i < n; ++i) {
            int count = 1;
            while (!s1.isEmpty() && s1.peek()[0] > A[i])
                count += s1.pop()[1];
            s1.push(new int[] {A[i], count});
            left[i] = count;
        }
        for (int i = n - 1; i >= 0; --i) {
            int count = 1;
            while (!s2.isEmpty() && s2.peek()[0] >= A[i])
                count += s2.pop()[1];
            s2.push(new int[] {A[i], count});
            right[i] = count;
        }
        for (int i = 0; i < n; ++i)
            res = (res + A[i] * left[i] * right[i]) % mod;
        return res;
    }

算法2

improve $O(n)$

blablabla

时间复杂度

参考文献

Java 代码

 public int sumSubarrayMins(int[] A) {
        int res = 0, len = A.length, mod = (int)1e9 + 7;
        Stack<Integer> s1 = new Stack<>();
        int j,k;
        for(int i = 0; i <= len; i++){
            int pivot = i == len ? 0:A[i];
            while(!s1.isEmpty() && pivot < A[s1.peek()]){
                j = s1.pop();
                k = s1.isEmpty() ? -1 : s1.peek();
                int llen = j - k;
                int rlen = i - j;
                res = (res + A[j] * llen * rlen) % mod;
            }
            s1.push(i);
        }
        return res;
    }