LeetCode 907. Sum of Subarray Minimums

原题链接在这里：https://leetcode.com/problems/sum-of-subarray-minimums/

题目：

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

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 <= arr.length <= 3 * 104
• 1 <= arr[i] <= 3 * 104

题解：

The minimum of subarray is straight forward. But how many subarrays containing this minimum value needs proof.

e.g. arr = [2, 9, 7, 8, 3, 4, 6, 1].

The element 3, there are 2 on its left, the distance is m = 4. There is 1 on its right, the distance is n = 3.

Overall, there are total m * n = 12 subarrays containing 3.

There are total m + n - 1 elements. The number of non-empty subarrays S3 is (1 + m + n - 1) * (m + n - 1) / 2.

On 3's left, [9, 8, 7]. The number of subarrays S1 = (1 + m - 1) * (m - 1) / 2.

One 3's right, [4, 6]. The number of subarrays S2 = (1 + n - 1) * (n - 1) / 2.

The number of subarrays containing 3 is S3 - S1 - S2 = m * n.

Have a monotonic increasing stack maintain the index, when encounter arr[i] is smaller stack top. Then we get the next smaller, like 1 in the example.

First pop we get the minimum elelment like 3 in the example.

If the stack is not empty, peek and we get the previous smaller like 2 in the example. 

Then accumlate 3 * (left distance) * (right distance) to the sum.

Time Complexity: O(n). n = arr.length.

Space: O(n).

AC Java:

 1 class Solution {
 2     public int sumSubarrayMins(int[] arr) {
 3         if(arr == null || arr.length == 0){
 4             return 0;
 5         }
 6         
 7         long sum = 0;   
 8         Stack stk = new Stack<>();
 9         int n = arr.length;
10         for(int i = 0; i <= n; i++){
11             while(!stk.isEmpty() && arr[stk.peek()] > (i == n ? Integer.MIN_VALUE : arr[i])){
12                 int minIndex = stk.pop();
13                 int pre = stk.isEmpty() ? -1 : stk.peek();
14                 sum += (long)arr[minIndex] * (i - minIndex) * (minIndex - pre);
15             }
16             
17             stk.push(i);
18         }
19         
20         return (int)(sum % (long)(1e9 + 7));
21     }
22 }

跟上.