[LeetCode] 84.Largest Rectangle in Histogram (js)

문제 

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

각 막대의 너비가 1인 히스토그램의 막내 높이를 나타내는 정수 배열이 주어진다. 히스토그램에서 나올 수 있는 가장 큰 직사각형의 면적을 반환하라.

풀이 

  const stack = [];
  let maxArea = 0;

 

문제에 접근하기 위해서는 Histogram의 막대 인덱스를 저장할 stack과 최대 너비를 담을 maxArea 라는 두 개의 변수가 필요하다. 

 

for (let i = 0; i <= heights.length; i++) {
   stack.push(i);      
}

 

다음으로는 주어진 막대 만큼 순회하면서 stack에 인덱스를 넣어 줄 것이다. 

물론 stack에 인덱스 값을 넣어 주기 전에 새로이 높이와 너비를 구해 maxArea와 비교한다.

while ( stack.length && (i === heights.length || heights[i] < heights[stack[stack.length - 1]])) {
    const height = heights[stack.pop()];
    const width = stack.length === 0 
                ? i 
                : i - stack[stack.length - 1] - 1;
    maxArea = Math.max(maxArea, height * width);
}

 

while문은 다음의 조건을 가진다.

1. stack이 비어있지 않고

2. 히스토그램의 끝에 도달했거나 ( i === heights.length)

3. 현재 막대의 높이(heigths[i])가 막대의 높이보다 작은 경우 

const height = heights[stack.pop()]

 

루프 내부에서 주어진 index를 기준으로 한 직사각형의 면적을 계산할때 높이는 이전 값을 pop()하면서 구해진다. 

 const width = stack.length === 0 
            ? i 
            : i - stack[stack.length - 1] - 1;

직사각형 너비는 앞서 막대를 pop()하 후 스택이 비어있으면 pop()된 막대가 지금까지 가장 작은 막대로 너비는 현재의 인덱스인 i 가된다는 것을 의미한다. 그 밖의 경우는 i - stack[stack.lenght-1] -1 로 계산된다. stack[stack.lenght-1] 는 pop()된 인덱스의 바로 왼쪽에 있는 인덱스를 의미한다. 

 

 maxArea = Math.max(maxArea, height * width);

위에서 구한 너비와 높이로 직사각형의 크기를 구하고, 기존에 저장되어있던 maxArea값과 비교하여 더 큰 값을 담는다. 

 

답안

var largestRectangleArea = function(heights) {
    const stack = [];
    let maxArea = 0;

    for (let i = 0; i <= heights.length; i++) {
        while ( stack.length && (i === heights.length || heights[i] < heights[stack[stack.length - 1]])) {

            const height = heights[stack.pop()];
            const width = stack.length === 0 
                        ? i 
                        : i - stack[stack.length - 1] - 1;
            maxArea = Math.max(maxArea, height * width);
        }
        stack.push(i);
    }

    return maxArea
};