Monotonic Stack
Maintain a stack that is always increasing or decreasing. When you push a new element, pop all elements that violate the order — those are the elements for which the current one is the answer.
Time
O(n)
Space
O(n)
Recognize it when
- Next greater / next smaller element
- Stock span / daily temperatures
- Largest rectangle in histogram
Questions — ordered by difficulty
Next Greater Element I
For each element in nums1, find the next greater element in nums2.
Daily Temperatures
Given daily temperatures, return an array where answer[i] is the number of days until a warmer day.
Online Stock Span
Design a class that collects stock prices and returns the span (consecutive days with price ≤ today).
Largest Rectangle in Histogram
Find the area of the largest rectangle that can be formed in a histogram.
Trapping Rain Water (Stack)
Same problem as Trapping Rain Water (LC 42) — compute how much water an elevation map can trap after raining — but solved with a monotonic stack instead of two pointers. The stack approach processes water layer-by-layer horizontally, useful for building intuition from a different angle.
Maximal Rectangle
Given a binary matrix, find the largest rectangle containing only 1s.
Sum of Subarray Minimums
Find the sum of the minimum element of every subarray of a given array.
Car Fleet
Find how many car fleets will arrive at the destination. Cars cannot pass each other.