Monotonic Stack

🏔️ The Mountain Lookout: Mastering Monotonic Stacks

Imagine you’re standing in a line of people of different heights, trying to see who’s taller than you ahead. That’s exactly what a Monotonic Stack helps computers figure out—super fast!

🎯 What You’ll Master Today

• Next Greater / Smaller Element Pattern – Finding who’s “taller” or “shorter” ahead
• Monotonic Stack – A special organized stack
• Daily Temperatures – When will it get warmer?
• Largest Rectangle in Histogram – Finding the biggest box in a bar chart

🌟 The Big Picture: What is a Monotonic Stack?

Think of a Line at a Water Slide 🎢

Imagine kids lined up for a water slide. The rule is: only kids who are taller than everyone behind them can see the slide.

A Monotonic Stack is like organizing this line so that:

• Everyone in line is arranged in ORDER (either all getting taller, or all getting shorter)
• When a new kid joins, shorter kids who can’t see anymore leave the line

Two Types:

1. Monotonic Increasing – Each person is taller than the one before (like stairs going UP)
2. Monotonic Decreasing – Each person is shorter than the one before (like stairs going DOWN)

graph TD
    A["📚 Regular Stack"] --> B["Items in any order"]
    C["📊 Monotonic Stack"] --> D["Items in sorted order!"]
    D --> E["Increasing: 1→3→5→7"]
    D --> F["Decreasing: 7→5→3→1"]

🔍 Pattern 1: Next Greater Element

The Playground Story 🎪

Imagine 5 kids standing in a line with numbers on their shirts: [4, 5, 2, 10, 8]

Each kid asks: “Who’s the first person TALLER than me on my RIGHT?”

How Monotonic Stack Solves This ⚡

Instead of each kid checking everyone (slow!), we use a clever trick:

Walk BACKWARDS through the line!

// Next Greater Element - Simple!
int[] nextGreater(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    Stack<Integer> stack = new Stack<>();

    // Start from the END
    for (int i = n - 1; i >= 0; i--) {
        // Remove smaller elements
        while (!stack.isEmpty() &&
               stack.peek() <= nums[i]) {
            stack.pop();
        }
        // What's left is next greater!
        result[i] = stack.isEmpty()
                    ? -1 : stack.peek();
        stack.push(nums[i]);
    }
    return result;
}

Visual Walkthrough 🎬

For array [4, 5, 2, 10, 8]:

graph TD
    A["Start from RIGHT"] --> B["i=4: Stack empty → -1"]
    B --> C["Push 8 → Stack: [8]"]
    C --> D["i=3: 8 < 10, pop → -1"]
    D --> E["Push 10 → Stack: [10]"]
    E --> F["i=2: 10 > 2 → result=10"]
    F --> G["Push 2 → Stack: [10,2]"]
    G --> H["i=1: pop 2, 10>5 → result=10"]
    H --> I["i=0: 5>4 → result=5"]

Result: [5, 10, 10, -1, -1] ✨

🔍 Pattern 2: Next Smaller Element

Same idea, but now each kid asks: “Who’s SHORTER than me on my right?”

The only change: we keep a Monotonic Increasing Stack instead!

// Next Smaller Element
int[] nextSmaller(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    Stack<Integer> stack = new Stack<>();

    for (int i = n - 1; i >= 0; i--) {
        // Remove LARGER elements now!
        while (!stack.isEmpty() &&
               stack.peek() >= nums[i]) {
            stack.pop();
        }
        result[i] = stack.isEmpty()
                    ? -1 : stack.peek();
        stack.push(nums[i]);
    }
    return result;
}

For [4, 5, 2, 10, 8]:

• 4 → 2 (smaller is ahead)
• 5 → 2
• 2 → -1 (nothing smaller)
• 10 → 8
• 8 → -1

Result: [2, 2, -1, 8, -1]

🌡️ Real Problem: Daily Temperatures

The Weather Story ☀️

You have a list of temperatures for each day. For each day, you want to know: “How many days until it’s warmer?”

Example: temperatures = [73, 74, 75, 71, 69, 72, 76, 73]

The Solution 🧠

We store indices (day numbers) in our stack, not temperatures!

int[] dailyTemperatures(int[] temps) {
    int n = temps.length;
    int[] answer = new int[n];
    Stack<Integer> stack = new Stack<>();

    for (int i = 0; i < n; i++) {
        // While current is warmer than
        // days in stack
        while (!stack.isEmpty() &&
               temps[i] > temps[stack.peek()]) {
            int prevDay = stack.pop();
            answer[prevDay] = i - prevDay;
        }
        stack.push(i);
    }
    return answer;
}

Why This Works 💡

graph TD
    A["Stack holds INDICES"] --> B["When warmer day found"]
    B --> C["Pop colder days"]
    C --> D["Calculate: today - that day"]
    D --> E["That's the wait time!"]

Key Insight: We go LEFT to RIGHT. When we find a warmer day, all the colder days waiting in the stack finally get their answer!

📊 Largest Rectangle in Histogram

The Building Story 🏗️

Imagine you have bars of different heights. You want to find the biggest rectangle you can draw using these bars.

Example: heights = [2, 1, 5, 6, 2, 3]

     ██
   ████
   ████
   ████  ██
██ ████████
██████████

The largest rectangle has area = 10 (using heights 5 and 6, width 2)

Why is This Hard? 🤔

For each bar, we need to know:

1. How far LEFT can we extend? (until we hit a shorter bar)
2. How far RIGHT can we extend? (until we hit a shorter bar)

This is exactly the Next Smaller Element pattern—TWICE!

The Complete Solution 🎯

int largestRectangle(int[] heights) {
    int n = heights.length;
    int[] leftSmaller = new int[n];
    int[] rightSmaller = new int[n];
    Stack<Integer> stack = new Stack<>();

    // Find left boundaries
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() &&
               heights[stack.peek()] >= heights[i]) {
            stack.pop();
        }
        leftSmaller[i] = stack.isEmpty()
                         ? -1 : stack.peek();
        stack.push(i);
    }

    stack.clear();

    // Find right boundaries
    for (int i = n - 1; i >= 0; i--) {
        while (!stack.isEmpty() &&
               heights[stack.peek()] >= heights[i]) {
            stack.pop();
        }
        rightSmaller[i] = stack.isEmpty()
                          ? n : stack.peek();
        stack.push(i);
    }

    // Calculate max area
    int maxArea = 0;
    for (int i = 0; i < n; i++) {
        int width = rightSmaller[i] - leftSmaller[i] - 1;
        int area = heights[i] * width;
        maxArea = Math.max(maxArea, area);
    }
    return maxArea;
}

Step-by-Step for [2, 1, 5, 6, 2, 3]

Maximum Area = 10 🎉

🎪 The Grand Summary

graph LR
    A["🏔️ MONOTONIC STACK"] --> B["Next Greater Element"]
    A --> C["Next Smaller Element"]
    A --> D["Daily Temperatures"]
    A --> E["Largest Rectangle"]

    B --> F["Decreasing Stack"]
    C --> G["Increasing Stack"]
    D --> H["Store indices, not values"]
    E --> I["Two passes: left + right"]

When to Use Monotonic Stack? 🎯

The Golden Rule 🌟

Monotonic Stack = O(n) magic for “find next bigger/smaller” problems!

Each element enters the stack once, leaves once = Linear time!

🎓 You Made It!

You now understand:

• ✅ What makes a stack “monotonic”
• ✅ How to find next greater/smaller elements in O(n)
• ✅ The Daily Temperatures pattern
• ✅ How to tackle the Largest Rectangle in Histogram

Remember: When you see “next greater/smaller” or “how many until bigger”—think Monotonic Stack! 🚀