Monotonic Stack
LC #907Hard
Sum of Subarray Minimums
Monotonic Stack
AmazonGoogleBloombergProblem
Find the sum of the minimum element of every subarray of a given array.
monotonic-stackdynamic-programming
Constraints
- ›1 ≤ arr.length ≤ 3×10⁴
- ›1 ≤ arr[i] ≤ 3×10⁴
- ›Answer mod 10⁹+7
Example
Input
arr = [3, 1, 2, 4]Output
17Why
Subarrays: [3]=3,[1]=1,[2]=2,[4]=4,[3,1]=1,[1,2]=1,[2,4]=2,[3,1,2]=1,[1,2,4]=1,[3,1,2,4]=1 → sum=17