Core Concept

The monotonic stack is a powerful technique for solving next greater elemant problems efficiently. The key insight is to maintain a stack that keeps candidate elements in a specific order, allowing us to find the next greater element for each position in a single pass.

Fundamental Example

Problem: Given an array, find the next greater element for each position. If no greater element exists to the right, return -1.

Input: [2, 5, 9, 3, 1, 12, 6, 8, 7]

Output: [5, 9, 12, 12, 12, -1, 8, -1, -1]

The algorithm processes the array from right to left while maintaining a monotonic decreasing stack. When encountering a new element, we pop smaller elements from the stack since they can never serve as the next greater element for any position to the left.

function findNextGreaterElements(arr) {
  const result = new Array(arr.length).fill(-1);
  const monoStack = [];
  
  for (let i = arr.length - 1; i >= 0; i--) {
    while (monoStack.length > 0 && arr[i] >= monoStack[monoStack.length - 1]) {
      monoStack.pop();
    }
    result[i] = monoStack.length > 0 ? monoStack[monoStack.length - 1] : -1;
    monoStack.push(arr[i]);
  }
  
  return result;
}

const input = [2, 5, 9, 3, 1, 12, 6, 8, 7];
console.log(findNextGreaterElements(input));

LeetCode 739: Daily Temperatures

Given an array of daily temperatures, return how many days until a warmer temperature arrives. If no warmer day exists, use 0.

function getDaysUntilWarmer(temps) {
  const days = new Array(temps.length).fill(0);
  const indexStack = [];
  
  for (let i = temps.length - 1; i >= 0; i--) {
    while (indexStack.length > 0 && temps[i] >= temps[indexStack[indexStack.length - 1]]) {
      indexStack.pop();
    }
    days[i] = indexStack.length > 0 ? indexStack[indexStack.length - 1] - i : 0;
    indexStack.push(i);
  }
  
  return days;
}

LeetCode 496: Next Greater Element I

Given two arrays where nums1 is a subset of nums2, find the next greater element for each element in nums1 within nums2.

The approach involves first computing the next greater element for every value in nums2, then using a hash map to retrieve results for nums1 elements.

function findNextGreater(nums1, nums2) {
  const answer = new Array(nums1.length).fill(-1);
  const valueToNext = new Map();
  const tempStack = [];
  
  for (let i = nums2.length - 1; i >= 0; i--) {
    while (tempStack.length > 0 && nums2[i] >= tempStack[tempStack.length - 1]) {
      tempStack.pop();
    }
    valueToNext.set(nums2[i], tempStack.length > 0 ? tempStack[tempStack.length - 1] : -1);
    tempStack.push(nums2[i]);
  }
  
  for (let j = 0; j < nums1.length; j++) {
    answer[j] = valueToNext.get(nums1[j]);
  }
  
  return answer;
}

Key Takeaways

The monotonic stack pattern excels at O(n) solutions for next greater element problems. The stack maintains potential candidates while we iterate through the array, and we always pop elements that are smaller than or equal to the current element. This ensures each element enters and leaves the stack at most once, yielding linear time complexity.