AdvancedAdvanced
Monotonic Stack/Queue
Maintain a stack or deque where elements are always in sorted order, enabling efficient next-greater/smaller element queries.
Problem: Next Greater Element
For each element in [4, 5, 2, 10, 8], find the next greater element to the right.
4
5
2
10
8
i
Stack (decreasing monotonic)
4
← bottom | top →
Result (Next Greater Elements)
?
?
?
?
?
Push arr[0] = 4 onto stack
Start with first element. Stack is empty, so push 4.
Step 1/7
Speed:
When to Use
- Next greater/smaller element
- Largest rectangle in histogram
- Sliding window maximum
- Stock span problem
Key Indicators
- Next greater/smaller element
- Histogram problems
- Sliding window max/min
- Temperature/stock problems
Complexity
Time
O(n)
Space
O(n)
Common Problems
Next Greater ElementDaily TemperaturesLargest Rectangle in HistogramSliding Window MaximumStock Span ProblemTrapping Rain Water (stack approach)
Code
stack = []
for i in range(n):
while stack and arr[stack[-1]] < arr[i]:
idx = stack.pop()
result[idx] = arr[i] # next greater
stack.append(i)Want all 29 patterns with detailed visual walkthroughs?
The complete book includes 84 practice problems, full decision tree, and illustrated step-by-step solutions.
Book Coming Soon ($4.99)