LeetCode [907] Sum of Subarray Minimums

 907. Sum of Subarray Minimums

Medium

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:

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. 1 <= A.length <= 30000
2. 1 <= A[i] <= 30000

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

class Solution { public int sumSubarrayMins(int[] A) { int M = 1000000007; int n = A.length; int[] lb = new int[n];//lb[i] is the previous index with A[lb[i]]<A[i] Arrays.fill(lb, -1);//lb[i] = -1 means i-th element does not have a smaller element to its left Stack<Integer> stk = new Stack<>(); for(int i=0; i<n; ++i){ while(!stk.empty() && A[stk.peek()]>=A[i]){ stk.pop(); } if(!stk.isEmpty()) lb[i] = stk.peek(); stk.push(i); } int[] rb = new int[n]; Arrays.fill(rb, n); stk.clear(); for(int i=n-1; i>=0; --i){ while(!stk.isEmpty() && A[stk.peek()]>A[i]){ stk.pop(); } if(!stk.isEmpty()) rb[i] = stk.peek(); stk.push(i); } int s = 0; for(int i=0; i<n; ++i){ s = (s + A[i]*(i-lb[i])*(rb[i]-i))%M; } return s; } }