Topic 42 of 78
Monotonic Stack
Overview
A Monotonic Stack is a normal Stack where the elements are kept strictly increasing or strictly decreasing from bottom to top. You push elements onto the stack, but before pushing, you pop off any elements that would violate the monotonic property. This structure is a 'cheat code' for a very specific class of interview problems: finding the 'Next Greater Element' or 'Next Smaller Element' in an array in O(N) time.
Syntax
By popping smaller elements when a larger one arrives, every element is pushed and popped exactly once, achieving O(N) time complexity instead of O(N^2).
Next Greater Element Pattern
java
public int[] nextGreaterElement(int[] nums) {
int n = nums.length;
int[] result = new int[n];
Arrays.fill(result, -1);
// Monotonic Decreasing Stack (stores indices, not values)
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
// While the current element is GREATER than the element at the stack's top index
while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
int topIndex = stack.pop();
// We found the next greater element for the popped index!
result[topIndex] = nums[i];
}
// Push the current index
stack.push(i);
}
return result;
}Common Pitfalls
- Storing values instead of indices in the stack, making it impossible to calculate the distance/width between elements.
- Getting confused between Monotonic Increasing vs Decreasing. For 'Next Greater Element', use a Decreasing stack.
Interview Tips
- Whenever an interview question asks for the 'Next Greater', 'Next Smaller', 'Previous Greater', or 'Daily Temperatures', instantly think Monotonic Stack.
Real-World Example
Financial applications use Monotonic Stacks to calculate the 'span' of stock prices (how many consecutive days prior was the price lower than today).
example
java
public int[] calculateSpan(int[] prices) {
int[] span = new int[prices.length];
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < prices.length; i++) {
while (!stack.isEmpty() && prices[stack.peek()] <= prices[i]) {
stack.pop();
}
// If stack is empty, it's greater than everything before it
span[i] = stack.isEmpty() ? (i + 1) : (i - stack.peek());
stack.push(i);
}
return span;
}