A Monotonic Stack is a stack that maintains its elements in a specific order: either strictly increasing or strictly decreasing. It is a powerful pattern used to solve "range" problems where you need to find the first element to the left or right that meets a criteria.

Imagine a line of people of different heights:

• You want every person in the line to be taller than the person behind them.
• If a short person is already at the end of the line and a taller person arrives:
  • The short person is "kicked out" (Popped) because their "range" of being the tallest is over.
• The new tall person becomes the new end of the line.

---

Why use it?

Many problems ask: "What is the first element to the right that is larger than the current one?"

• Brute Force: $O(n^2)$ using nested loops.
• Monotonic Stack: $O(n)$ because each element is pushed and popped exactly once.

Types

1. Monotonic Increasing: [1, 3, 5, 8]. When a smaller element arrives, we pop larger elements.
2. Monotonic Decreasing: [10, 8, 5, 2]. When a larger element arrives, we pop smaller elements.

---

javascript Standard
/**
 * Finding the Next Greater Element for every item in an array.
 * If no greater element exists, use -1.
 */
function nextGreaterElement(nums) {
  const n = nums.length;
  const result = new Array(n).fill(-1);
  const stack = []; // Storing Indices

  for (let i = 0; i < n; i++) {
    /**
     * While stack is not empty and current element is 
     * GREATER than the element at the top index...
     */
    while (stack.length > 0 && nums[i] > nums[stack[stack.length - 1]]) {
      // The current element is the "Next Greater" for the top of the stack
      const index = stack.pop();
      result[index] = nums[i];
    }
    
    // Push current index to find its next greater later
    stack.push(i);
  }

  return result;
}

// Example
console.log(nextGreaterElement([2, 1, 2, 4, 3])); 
// [4, 2, 4, -1, -1]

---

Key Patterns

• "Next Greater/Smaller Element": The #1 indicator.
• "Previous Greater/Smaller Element": Just process the array from right to left or adjust the loop.
• "Remaining Area/Range": Problems involving building heights or histograms.

Must-Practice Problems

• Daily Temperatures: Find how many days you have to wait for a warmer day.
• Largest Rectangle in Histogram: A classic hard problem using monotonic stacks.
• Trapping Rain Water: Can be solved with monotonic stacks or two pointers.
• Online Stock Span: Find the number of consecutive days the price was less than today.