Approach Summary
Monotonic stack to find for each element how many subarrays it is the minimum of (left boundary × right boundary). Sum contributions.
How to Recognize This Pattern
- "Sum of minimums of all subarrays"
- For each element, count subarrays where it's the min
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(n)
Tags
Array Dynamic Programming Stack Monotonic Stack