Monotonic Stack | Algorithms & Data Structures

Algorithm Summary

A monotonic stack keeps its elements in consistently increasing or decreasing order. Each index is pushed and popped at most once, so the full traversal is O(n).

Use it for one-dimensional arrays when the problem asks for the first value to the left or right that is greater or smaller than the current value. Store indices rather than values when the answer needs a distance, width, or original position.

Examples

Daily Temperatures — LC 739

Maintain indices whose next warmer day has not been found. When the current temperature exceeds the temperature at the top index, pop that index and record the distance.

Java

public int[] dailyTemperatures(int[] temperatures) {
    int[] result = new int[temperatures.length];
    Deque<Integer> stack = new ArrayDeque<>();

    for (int i = 0; i < temperatures.length; i++) {
        while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            int previous = stack.pop();
            result[previous] = i - previous;
        }
        stack.push(i);
    }
    return result;
}

Next Greater Element I — LC 496

Run the next-greater pattern over nums2 and save each value's answer in a map. Then look up the values requested by nums1.

Next Greater Element II — LC 503

The array is circular. Traverse 2 * n positions and access values with i % n, while writing answers only for original indices.

Java

for (int i = 0; i < 2 * n; i++) {
    int index = i % n;
    while (!stack.isEmpty() && nums[index] > nums[stack.peek()]) {
        result[stack.pop()] = nums[index];
    }
    if (i < n) stack.push(index);
}

Trapping Rain Water — LC 42

Keep a decreasing stack of bar indices. When a taller right wall appears, the popped bar is the basin floor, the new top is the left wall, and the current bar is the right wall.

Plain text

left wall        right wall
    █                █
    █  ~  ~  ~  ~   █
    █     floor      █

The trapped height is min(leftHeight, rightHeight) - floorHeight; the width is rightIndex - leftIndex - 1.

Java

while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
    int floor = stack.pop();
    if (stack.isEmpty()) break;
    int boundedHeight = Math.min(height[i], height[stack.peek()]) - height[floor];
    int width = i - stack.peek() - 1;
    water += boundedHeight * width;
}

Largest Rectangle in Histogram — LC 84

For every bar, find the first smaller bar on both sides. Maintain an increasing stack and calculate an area whenever a shorter bar closes the current rectangle. Add zero-height sentinels at both ends so strictly increasing and decreasing inputs use the same logic.

Java

while (!stack.isEmpty() && heights[i] < heights[stack.peek()]) {
    int heightIndex = stack.pop();
    int width = i - stack.peek() - 1;
    result = Math.max(result, heights[heightIndex] * width);
}