Given an array A of integers, 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:
Input: [3,1,2,4]
Output: 17
Constraints:
1<=A.size<=30000
1<=A[i]<=30000
Solution:
We maintain 2 arrays, pre, next, where pre[i] stores the index of the element which is less than A[i] and the index is less than 'i' if there is no such element we store -1.
Similarly in the array next, next[i] stores the index element which is less than A[i] and the index is greater than i.
Now we iterate over the original array A, and for every array element it forms (i-pre[i])*(next[i]-i) number of subarrays.
Code:
# define mod 1000000007
int sumSubarrayMins(vector<int>& A) {
int n=A.size();
long ans=0;
vector<int> pre(n),next(n);
stack<int> st1,st2;
for(int i=0;i<n;i++)
{
while(!st1.empty()&&A[i]<=A[st1.top()])
st1.pop();
pre[i]=st1.empty()?-1:st1.top();
st1.push(i);
}
for(int i=n-1;i>=0;i--)
{
while(!st2.empty()&&A[i]<A[st2.top()])
st2.pop();
next[i]=st2.empty()?n:st2.top();
st2.push(i);
}
for(int i=0;i<n;i++)
{
ans+=(i-pre[i])*(next[i]-i)%mod*A[i]%mod;
ans%=mod;
}
return (int)ans;
}
Programming ninja
If you have any doubts or any new insights, please share ConversionConversion EmoticonEmoticon