Stacks & Queues
LIFO and FIFO structures for expression parsing, monotonic sequences, and design
0/41 solved
Monotonic Stack
Maintain a stack of increasing/decreasing elements for next-greater/smaller problems
Approach
Maintain a stack that preserves a monotonic order. When processing a new element, pop all elements from the stack that violate the monotonic property — each popped element has found its answer (the current element). Push the current element onto the stack.
How to Recognize
Problem asks for the next greater or next smaller element
Need to find the nearest larger/smaller element to the left or right
Histogram or water trapping type problems
Phrases like 'daily temperatures', 'stock span'
Pro Tips
Decreasing stack for next greater element, increasing stack for next smaller
Process elements right-to-left to find next greater to the right
The stack stores indices (not values) when you need positional information
9
Total
1
Easy
5
Medium
3
Hard
Time
O(n)
Space
O(n)