LeetCode - 84. Largest Rectangle in Histogram

Thoughts:

I choose stack to solve this problem.

The time complexity will be O(n).

Thoughts visuzlization:

heights = [1,2,3,1,1]

  x
 xx
xxxxx

maxArea = 0

stack = []
storing indice of heights
if the stack has elements and encounter a lower one
keep popping the index and calculating the area

  * calculation is like below
    1. h = heights[stack.pop()]
       use popped index to find the height
    2. w = stack.length === 0 ? i : i - stack[stack.length-1] - 1
       because heights has '0' at the end
       so every w not just substract the popped index, need to substract 1 additionally
       use i represents w if the stack is empty
    3. maxArea = Math.max(maxArea, w * h)

heights.push(0)
this step is tricky
because if the height grows higher
I don'e need to calculate anything
because the area keep being larger and larger
so if every height grows increasingly
the key problem will be when I need to calculate the area
let's why there should have a lowest height to calculate backward


heights = [1,2,3,1,1,0] stack = [0]
           i            maxArea = 0

heights = [1,2,3,1,1,0] stack = [0,1]
             i          maxArea = 0

heights = [1,2,3,1,1,0] stack = [0,1,2]
               i        maxArea = 0

heights = [1,2,3,1,1,0] stack = [0,1]
                 i      (3-1-1) * height[2] = 3
                        stack = [0]
                        (3-0-1) * height[1] = 4
                        maxArea = 4
                        stack = [0,3]

heights = [1,2,3,1,1,0] stack = [0,3,4]
                   i    maxArea = 4

heights = [1,2,3,1,1,0] stack = [0,3]
                     i  (5-3-1) * height[4] = 1
                        stack = [0]
                        (5-0-1) * height[3] = 4
                        stack = []
                        5 * height[0] = 5
                        maxArea = 5

Code:

/**
 * @param {number[]} heights
 * @return {number}
 */
var largestRectangleArea = function (heights) {
  let maxArea = 0;
  const stack = [];
  for (let i in heights) {
    while (stack.length > 0 && heights[stack[stack.length - 1]] > heights[i]) {
      const h = heights[stack.pop()];
      const w = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
      maxArea = Math.max(maxArea, w * h);
    }
    stack.push(i);
  }
  return maxArea;
};

Reference

Original link