Approach Summary
Monotonic increasing stack of indices. On smaller bar, pop and compute area using current index and new stack top as boundaries.
How to Recognize This Pattern
- Maximum rectangle area
- Histogram bars
- Stack with sentinel
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(n)
Tags
Array Stack Monotonic Stack