codaBack to Academy
patterns
Monotonic Stack
A monotonic stack maintains elements in either strictly increasing or decreasing order. When a new element violates the monotonic property, elements are popped until the property is restored. This pattern efficiently solves problems that require finding the next greater or smaller element for each position in an array.
Use Cases
- •Finding the next greater element for each position
- •Computing the largest rectangle in a histogram
- •Calculating stock span or daily temperatures
Complexity Analysis
| Metric | Best | Average | Worst |
|---|---|---|---|
| Time | O(n) | O(n) | O(n) |
| Space | O(n) | ||
Visualization
Stack:[]
Result:[-, -, -, -, -]
Implementation
Output
Click "Run Code" to see output...