18 — Monotonic Stack & Queue

Monotonic Stack

Stack that maintains elements in increasing or decreasing order.

Monotonic Increasing Stack: bottom → top is ascending
  Push: pop all elements > current, then push
  Use: find next SMALLER element

Monotonic Decreasing Stack: bottom → top is descending
  Push: pop all elements < current, then push
  Use: find next GREATER element

---

Next Greater Element

function nextGreaterElement(nums: number[]): number[] {
  const n = nums.length;
  const result = new Array(n).fill(-1);
  const stack: number[] = []; // Stores indices
  
  for (let i = 0; i < n; i++) {
    while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
      result[stack.pop()!] = nums[i];
    }
    stack.push(i);
  }
  return result;
}

// [2, 1, 5, 3, 4] → [5, 5, -1, 4, -1]

Next Smaller Element

function nextSmallerElement(nums: number[]): number[] {
  const n = nums.length;
  const result = new Array(n).fill(-1);
  const stack: number[] = [];
  
  for (let i = 0; i < n; i++) {
    while (stack.length && nums[stack[stack.length - 1]] > nums[i]) {
      result[stack.pop()!] = nums[i];
    }
    stack.push(i);
  }
  return result;
}

---

Largest Rectangle in Histogram

function largestRectangleArea(heights: number[]): number {
  const stack: number[] = []; // Indices of increasing heights
  let maxArea = 0;
  
  for (let i = 0; i <= heights.length; i++) {
    const h = i === heights.length ? 0 : heights[i];
    
    while (stack.length && heights[stack[stack.length - 1]] > h) {
      const height = heights[stack.pop()!];
      const width = stack.length ? i - stack[stack.length - 1] - 1 : i;
      maxArea = Math.max(maxArea, height * width);
    }
    stack.push(i);
  }
  return maxArea;
}

// [2, 1, 5, 6, 2, 3] → 10 (5×2 rectangle at indices 2-3)

---

Trapping Rain Water

function trap(height: number[]): number {
  const stack: number[] = [];
  let water = 0;
  
  for (let i = 0; i < height.length; i++) {
    while (stack.length && height[i] > height[stack[stack.length - 1]]) {
      const bottom = stack.pop()!;
      if (!stack.length) break;
      const left = stack[stack.length - 1];
      const w = i - left - 1;
      const h = Math.min(height[i], height[left]) - height[bottom];
      water += w * h;
    }
    stack.push(i);
  }
  return water;
}

// Two-pointer approach (simpler):
function trap2(height: number[]): number {
  let lo = 0, hi = height.length - 1;
  let leftMax = 0, rightMax = 0, water = 0;
  
  while (lo < hi) {
    if (height[lo] < height[hi]) {
      leftMax = Math.max(leftMax, height[lo]);
      water += leftMax - height[lo];
      lo++;
    } else {
      rightMax = Math.max(rightMax, height[hi]);
      water += rightMax - height[hi];
      hi--;
    }
  }
  return water;
}

---

Daily Temperatures

// Days until warmer temperature
function dailyTemperatures(temps: number[]): number[] {
  const n = temps.length;
  const result = new Array(n).fill(0);
  const stack: number[] = [];
  
  for (let i = 0; i < n; i++) {
    while (stack.length && temps[stack[stack.length - 1]] < temps[i]) {
      const j = stack.pop()!;
      result[j] = i - j;
    }
    stack.push(i);
  }
  return result;
}

---

Sliding Window Maximum (Monotonic Deque)

function maxSlidingWindow(nums: number[], k: number): number[] {
  const deque: number[] = []; // Indices, decreasing values
  const result: number[] = [];
  
  for (let i = 0; i < nums.length; i++) {
    // Remove elements outside window
    while (deque.length && deque[0] <= i - k) deque.shift();
    
    // Remove smaller elements (they'll never be max)
    while (deque.length && nums[deque[deque.length - 1]] <= nums[i]) deque.pop();
    
    deque.push(i);
    
    if (i >= k - 1) result.push(nums[deque[0]]); // Front is always the max
  }
  return result;
}

// [1,3,-1,-3,5,3,6,7], k=3 → [3,3,5,5,6,7]

---

Pattern Summary

---

Key Takeaways

• Monotonic stack: O(n) for "next greater/smaller" problems — each element pushed/popped once
• Decreasing stack → next greater; Increasing stack → next smaller
• Largest rectangle: classic monotonic stack — height from popped, width from gap
• Sliding window max: monotonic deque — remove expired from front, smaller from back
• These patterns appear frequently in interviews — recognize the "next X element" structure