Monotonic Stack Problems (72)

A Monotonic Stack is a powerful data structure technique used in algorithm design to maintain elements in either increasing or decreasing order while processing them sequentially. Instead of storing arbitrary values like a regular Stack, a monotonic stack enforces an order: elements are pushed and popped so the stack always stays monotonically increasing or decreasing. This property allows you to efficiently answer questions about the next greater element, previous smaller element, ranges, and boundaries in linear time.

Monotonic stacks frequently appear in coding interviews because they convert seemingly complex problems into O(n) solutions. Many problems that look like they require nested loops can be solved in a single pass using this technique. Companies often test it through classic problems such as Next Greater Element, Largest Rectangle in Histogram, and Daily Temperatures. These problems typically start with an Array and require identifying the nearest greater or smaller value on either side of each element.

Common monotonic stack patterns include:

• Next greater / next smaller element problems
• Previous greater / previous smaller element lookups
• Range expansion problems such as histogram or subarray boundaries
• Combining stacks with techniques like Sliding Window or greedy decisions from Greedy algorithms

You should consider using a monotonic stack when a problem asks for the nearest larger or smaller element to the left or right, or when you need to process elements while maintaining order constraints. It is also closely related to the Monotonic Queue, which extends the same idea for sliding window scenarios.

On FleetCode, you can master this pattern through 62 Monotonic Stack problems that gradually increase in difficulty. By practicing these questions and recognizing the core patterns, you'll learn how to quickly identify when this technique can transform a brute-force solution into an optimal linear-time algorithm—an essential skill for technical interviews.