Monotonic stack is one of those patterns that looks magical until you understand the invariant it maintains. Next greater element, largest rectangle in histogram, daily temperatures — all solved with the same idea.
A monotonic stack maintains an invariant — elements are always in increasing or decreasing order. This invariant lets you answer 'next greater/smaller element' questions in O(n) instead of O(n²).
1// For each element, find the next element that is greater
2// Monotonic decreasing stack (top is smallest)
3public int[] nextGreaterElement(int[] nums) {
4 int n = nums.length;
5 int[] result = new int[n];
6 Arrays.fill(result, -1);
7 Deque<Integer> stack = new ArrayDeque<>(); // stores indices
8
9 for (int i = 0; i < n; i++) {
10 // Pop elements smaller than current — current is their "next greater"
11 while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
12 result[stack.pop()] = nums[i];
13 }
14 stack.push(i);
15 }
16 return result;
17}1public int largestRectangleArea(int[] heights) {
2 Deque<Integer> stack = new ArrayDeque<>();
3 int maxArea = 0;
4 int n = heights.length;
5
6 for (int i = 0; i <= n; i++) {
7 int h = (i == n) ? 0 : heights[i];
8 while (!stack.isEmpty() && heights[stack.peek()] > h) {
9 int height = heights[stack.pop()];
10 int width = stack.isEmpty() ? i : i - stack.peek() - 1;
11 maxArea = Math.max(maxArea, height * width);
12 }
13 stack.push(i);
14 }
15 return maxArea;
16}Monotonic increasing stack → use for 'next smaller element' or 'largest rectangle'. Monotonic decreasing stack → use for 'next greater element' or 'max sliding window'. The invariant tells you exactly when to pop.
1public int[] dailyTemperatures(int[] temps) {
2 int[] result = new int[temps.length];
3 Deque<Integer> stack = new ArrayDeque<>();
4 for (int i = 0; i < temps.length; i++) {
5 while (!stack.isEmpty() && temps[stack.peek()] < temps[i]) {
6 int idx = stack.pop();
7 result[idx] = i - idx;
8 }
9 stack.push(i);
10 }
11 return result;
12}A harder monotonic stack problem. For each element, find how many subarrays it is the minimum of. This requires finding the previous smaller element (left boundary) and next smaller element (right boundary) — two monotonic stack passes.
1public int sumSubarrayMins(int[] arr) {
2 int MOD = 1_000_000_007, n = arr.length;
3 int[] left = new int[n], right = new int[n];
4 Deque<Integer> stack = new ArrayDeque<>();
5
6 // Distance to previous smaller element
7 for (int i = 0; i < n; i++) {
8 while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) stack.pop();
9 left[i] = stack.isEmpty() ? i + 1 : i - stack.peek();
10 stack.push(i);
11 }
12 stack.clear();
13 // Distance to next smaller or equal element
14 for (int i = n - 1; i >= 0; i--) {
15 while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) stack.pop();
16 right[i] = stack.isEmpty() ? n - i : stack.peek() - i;
17 stack.push(i);
18 }
19
20 long ans = 0;
21 for (int i = 0; i < n; i++)
22 ans = (ans + (long) arr[i] * left[i] * right[i]) % MOD;
23 return (int) ans;
24}Monotonic stack problems often require you to store indices, not values. You need the index to compute distances (how far left/right until a boundary). Store indices, look up values via arr[idx].
More in DSA