04-stack

04 · Stack

Last-In-First-Out — perfect for "match the most recent thing" problems.

🧠 Intuition

A stack shines when the current element's fate depends on the most recently seen unresolved element: matching brackets, undo, or a monotonic stack that keeps elements in increasing/decreasing order to answer "next greater" queries.

🕵️ When to reach for it

• Balanced parentheses / nesting.
• "Next greater / smaller element", "days until warmer".
• Evaluating expressions (RPN).

🧩 Template (monotonic stack)

Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
    while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
        int idx = stack.pop();   // arr[i] is the "next greater" for idx
    }
    stack.push(i);
}

📝 Problems

Problem	Difficulty	Solution
Valid Parentheses	🟢	todo
Min Stack	🟡	todo
Evaluate Reverse Polish Notation	🟡	todo
Daily Temperatures	🟡	todo
Car Fleet	🟡	todo
Largest Rectangle in Histogram	🔴	todo