Monotonic Stack Pattern Java

Direct Answer

A monotonic stack keeps its elements in sorted order (always increasing or always decreasing) by popping any element that would break the order before pushing. It solves next/previous greater (or smaller) element problems in O(n) total - each element is pushed and popped at most once - instead of the O(n^2) brute force. Classic uses: daily temperatures, stock span, largest rectangle in histogram.

Deep Dive & Architecture

A monotonic stack stores unresolved candidates in increasing or decreasing order. When a new value breaks that order, it answers the question for one or more stored candidates before they are removed.

Worked example: daily temperatures [73, 74, 75, 71, 69, 72, 76, 73]

Store indexes whose warmer day is not known yet. Temperature 74 is warmer than 73, so pop index 0 and record a wait of 1 day. Temperature 75 resolves index 1. Values 71 and 69 remain stacked; when 72 arrives, it resolves 69 after 1 day and 71 after 2 days. Later 76 resolves 72, 75, and any smaller unresolved values.

Indexes are stored instead of only temperatures because the answer needs a distance. The stack is decreasing by temperature from bottom to top; every item on it is still waiting for a greater value to its right.

Although one new value may trigger several pops, each index is pushed once and popped at most once. Total time is therefore O(n), not O(n²), and space is O(n). Changing the comparison changes the problem: a decreasing stack finds next-greater values, while an increasing stack can find next-smaller values. Decide whether equal values should pop based on whether the question asks for strictly greater or greater-or-equal.

Code Example

int[] dailyTemperatures(int[] t) {
    int[] ans = new int[t.length];
    Deque<Integer> stack = new ArrayDeque<>();   // indices, decreasing temps
    for (int i = 0; i < t.length; i++) {
        while (!stack.isEmpty() && t[i] > t[stack.peek()]) {
            int j = stack.pop();        // i is the next warmer day for j
            ans[j] = i - j;             // distance in days
        }
        stack.push(i);
    }
    return ans;                         // leftover indices stay 0
}

// t = {73,74,75,71,69,72,76,73}
// ans = {1,1,4,2,1,1,0,0} - each index pushed/popped once -> O(n)

Common Mistakes & Pitfalls

• Thinking it's O(n^2): the nested while is amortized O(n) - each index enters/leaves once.
• Storing values not indices: distance-based answers (days, widths) need indices.
• Wrong monotonic direction: next-greater uses a decreasing stack; next-smaller uses increasing.
• Forgetting leftovers: indices still on the stack have no greater/smaller element (answer 0 / -1).