[Algorithm] 6.Monotonic stack

6.Monotonic stack

The Monotonic Stack pattern uses a stack to maintain a sequence of elements in a specific order (increasing or decreasing).

Use this pattern for problems that require finding the next greater or smaller element.

Next Greater Element I (LeetCode #496)

function nextGreaterElement(nums1: number[], nums2: number[]): number[] {
    const nextGreater = new Map<number, number>();
    const stack : number[] = [];


    for(let i = nums2.length - 1; i >= 0 ; i--){
        while(stack.length > 0 && stack[stack.length - 1 ] <= nums2[i]){
            stack.pop();
        }
        nextGreater.set(nums2[i], stack.length > 0 ? stack[stack.length - 1] : -1);
        stack.push(nums2[i])
    }

    return nums1.map(num => nextGreater.get(num));
};

Daily Temperatures (LeetCode #739)

export function dailyTemperatures(temperatures: number[]): number[] {
  // const nextGreater = new Map<number, number | null>();

  const answer = new Array(temperatures.length).fill(0);
  const stack: number[] = [];

  for (let i = 0; i < temperatures.length; i++) {
    while (
      stack.length > 0 &&
      temperatures[i] > temperatures[stack[stack.length - 1]]
    ) {
      const index = stack.pop()!;
      answer[index] = i - index;
    }

    // nextGreater.set(temperatures[i], stack.length > 0 ? i : null);
    //    nextGreater.set(temperatures[i], stack.length > 0 ? stack[stack.length - 1] : 0);
    // stack.push(temperatures[i]);
    stack.push(i);
  }

  return answer;
}

Largest Rectangle in Histogram (LeetCode #84)

// better performance
export function largestRectangleArea2Passed(heights: number[]): number {
  const stack: number[] = []; // Stack stores indices
  let maxArea = 0;

  // length + 1 runs
  // for (let i = 0; i <= heights.length; i++) {
  for (let i = 0; i < heights.length + 1; i++) {
    const currHeight = i < heights.length ? heights[i] : 0;

    while (stack.length > 0 && heights[stack[stack.length - 1]] > currHeight) {
     
      const height = heights[stack.pop()!]; // Pop top
      const width = stack.length > 0 ? i - stack[stack.length - 1] - 1 : i;
      maxArea = Math.max(maxArea, height * width);
     
    }

    stack.push(i);
  }

  return maxArea;
}

function largestRectangleArea(heights: number[]): number {
  const stack: [number, number][] = [];
  let maxArea = 0;

  for (let i = 0; i < heights.length; i++) {
    let start = i;

    while (stack.length > 0 && stack[stack.length - 1][1] > heights[i]) {
      const [index, height] = stack.pop()!;
      maxArea = Math.max(maxArea, height * (i - index));
      start = index;
    }

    stack.push([start, heights[i]]);
  }

  for (const [index, height] of stack) {
    maxArea = Math.max(maxArea, height * (heights.length - index));
  }

  return maxArea;
}