📉

Monotonic Decreasing Stack

Maintain a stack of indices in decreasing value order. When nums[i] > nums[stack.top()], the current index i is the Next Greater Element for every index we pop. Each element is pushed/popped at most once — O(n) total.

Next Greater Element Monotonic Stack O(n) Time O(n) Space O(n)

📋 When to Use

Find next greater element for each index in O(n)
Daily temperatures — how many days to wait for a warmer day
Stock span / price problems — consecutive days not exceeding today
Histogram pre-processing — left/right boundary for each bar
Any "pop when current beats top" scenario

💡 Key insight: when a larger element arrives, it is the NGE for everything smaller currently in the stack. Process them all in one sweep — no nested loops needed.

⚡ Complexity

Time

O(n)

Space

O(n)

Each element is pushed onto the stack exactly once and popped at most once — giving O(2n) = O(n) total operations. The stack holds at most n indices at any time, so space is O(n). Much better than the naive O(n²) brute-force.

⚠️ Each element pushed/popped at most once — amortized O(1) per element.

Problem Find the Next Greater Element for every index in nums = [2, 1, 3, 4, 2]. Iterate left-to-right. When nums[i] > nums[stack.top()], pop the top — i is its NGE. Keep popping while condition holds, then push i. Elements left in the stack when the loop ends have no NGE → −1.
Array: [2, 1, 3, 4, 2] · Answer: NGE = [3, 3, 4, −1, −1]

Step 1 / —

🔍 Check

📥 Push

💥 Pop+NGE

🏁 Done

Bar chart — nums = [2, 1, 3, 4, 2]

NGE result — result[i] (? = not yet found)

📚 Stack

bottom → top (left → right)

[ empty ]

Comparison will appear here once iteration starts

i = —

nums[i] = —

stack size = 0

step = 0

Click ▶ Play or Next ▶ to begin the animation

int[] result = new int[n]; Arrays.fill(result, -1);

Monotonic Decreasing Stack — Pattern SkeletonJAVA

// Monotonic Decreasing Stack — Next Greater Element
int[] result = new int[n];
Arrays.fill(result, -1);           // default: no NGE
Deque<Integer> stack = new ArrayDeque<>(); // stores indices

for (int i = 0; i < n; i++) {
    // Pop all indices whose value is smaller than nums[i]
    while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
        int idx = stack.pop();
        result[idx] = nums[i];     // i is NGE for idx
    }
    stack.push(i);                 // push current index
}
// Remaining in stack have no NGE (result stays -1)

🎯 Practice Problems

#739Daily TemperaturesMedium #496Next Greater Element IEasy #503Next Greater Element II (circular)Medium #901Online Stock SpanMedium