What makes a stack monotonic
A regular stack pushes and pops in LIFO order with no constraints on element ordering. A monotonic stack adds one rule: before pushing a new element, pop all elements that violate the desired ordering. In a monotonically decreasing stack (largest at bottom, smallest at top), before pushing x, you pop every element smaller than x. The crucial observation: every pop event answers a query. When you pop element y because x is larger, you have just discovered that x is the "next greater element" for y. This is what makes monotonic stacks so powerful — they find relationships between elements as a side effect of the push/pop operations.
Template: next greater element (monotonic decreasing)
Key decisions: (1) store indices not values in the stack — you need to look up both the value (for comparison) and the position (to record the answer). (2) Initialize result with -1 (the "no greater element found" sentinel). (3) The while loop processes ALL elements that the current element is greater than — not just one. Daily Temperatures (LC 739) uses exactly this template with nums[i] representing the temperature.
Code template
def next_greater_elements(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(n):
while stack and nums[i] > nums[stack[-1]]:
idx = stack.pop()
result[idx] = nums[i]
stack.append(i)
return resultpublic int[] nextGreaterElements(int[] nums) {
int n = nums.length;
int[] result = new int[n];
Arrays.fill(result, -1);
Deque<Integer> stack = new ArrayDeque<>(); // store indices, not values
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
int idx = stack.pop();
result[idx] = nums[i];
}
stack.push(i);
}
return result;
}vector<int> nextGreaterElements(const vector<int>& nums) {
int n = nums.size();
vector<int> result(n, -1);
vector<int> stk; // store indices, not values
for (int i = 0; i < n; i++) {
while (!stk.empty() && nums[i] > nums[stk.back()]) {
int idx = stk.back();
stk.pop_back();
result[idx] = nums[i];
}
stk.push_back(i);
}
return result;
}Template: largest rectangle (monotonic increasing)
The appended 0 flushes all remaining elements at the end. The width calculation uses the stack state to find the span — when the stack is empty, the bar extends all the way to the left boundary (width = i). This is the hardest monotonic stack template to derive from scratch; memorize it.
Code template
def largest_rectangle(heights):
stack = []
max_area = 0
heights = heights + [0]
for i, h in enumerate(heights):
while stack and h < heights[stack[-1]]:
height = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1
max_area = max(max_area, height * width)
stack.append(i)
return max_areapublic int largestRectangleArea(int[] heights) {
Deque<Integer> stack = new ArrayDeque<>();
int maxArea = 0;
int n = heights.length;
for (int i = 0; i <= n; i++) { // virtual 0 at the end flushes stack
int h = (i == n) ? 0 : heights[i];
while (!stack.isEmpty() && h < heights[stack.peek()]) {
int height = heights[stack.pop()];
int width = stack.isEmpty() ? i : i - stack.peek() - 1;
maxArea = Math.max(maxArea, height * width);
}
stack.push(i);
}
return maxArea;
}int largestRectangleArea(const vector<int>& heights) {
vector<int> stk;
int maxArea = 0;
int n = heights.size();
for (int i = 0; i <= n; i++) { // virtual 0 at the end flushes stack
int h = (i == n) ? 0 : heights[i];
while (!stk.empty() && h < heights[stk.back()]) {
int height = heights[stk.back()];
stk.pop_back();
int width = stk.empty() ? i : i - stk.back() - 1;
maxArea = max(maxArea, height * width);
}
stk.push_back(i);
}
return maxArea;
}LC 42: Trapping Rain Water with monotonic stack
Trapping Rain Water (LC 42) is most commonly solved with two pointers (O(1) space), but the monotonic stack approach generalizes better to 2D versions. For each bar popped from the stack (call it the "bottom"), the water trapped between it and the current bar is: min(heights[left_boundary], heights[current]) - heights[bottom]) * (current - left_boundary - 1). The stack approach processes water layer by layer from the bottom up, making it more intuitive than the two-pointer left_max/right_max approach. In interviews, mention both approaches and explain the tradeoff: two-pointer is O(1) space; stack is easier to extend to 2D.
Circular array variant: Next Greater Element II (LC 503)
When the array is circular (you can look past the end back to the beginning), run the same algorithm twice over the concatenated array — or use index modulo. Only record results for i < n (first pass). The modulo trick handles circularity without actual array duplication. This pattern applies to any "next X in a circular array" problem.
Code template
def next_greater_elements(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(2 * n):
idx = i % n
while stack and nums[idx] > nums[stack[-1]]:
result[stack.pop()] = nums[idx]
if i < n: # only push indices in the first pass
stack.append(idx)
return resultpublic int[] nextGreaterElements(int[] nums) {
int n = nums.length;
int[] result = new int[n];
Arrays.fill(result, -1);
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < 2 * n; i++) {
int idx = i % n;
while (!stack.isEmpty() && nums[idx] > nums[stack.peek()]) {
result[stack.pop()] = nums[idx];
}
if (i < n) stack.push(idx); // only push indices in the first pass
}
return result;
}vector<int> nextGreaterElements(const vector<int>& nums) {
int n = nums.size();
vector<int> result(n, -1);
vector<int> stk;
for (int i = 0; i < 2 * n; i++) {
int idx = i % n;
while (!stk.empty() && nums[idx] > nums[stk.back()]) {
result[stk.back()] = nums[idx];
stk.pop_back();
}
if (i < n) stk.push_back(idx); // only push indices in the first pass
}
return result;
}Recognizing monotonic stack in disguise
Not all monotonic stack problems announce themselves. Car Fleet (LC 853) seems like a simulation problem but the key insight is that cars arriving in order form a natural stack — faster cars catch up to slower ones and merge into fleets. Asteroid Collision (LC 735) is explicitly a stack problem but requires handling multiple collision cases that a monotonic stack naturally resolves. Online Stock Span (LC 901) is a "previous greater element" problem in streaming form. The unifying signal: you need to find the nearest element satisfying a condition — this is always monotonic stack territory.