[LeetCode] 84. Largest Rectangle in Histogram

다음과 같은 풀이 공식이 있는 문제이다.

1. 모든 막대를 순회한다.
2. 각 막대는 stack자료 형태로 보관된다.
3. 만일 i번째의 막대 높이가 stack에 저장된 마지막 높이의 막대보다 낮을 경우 다음 로직을 수행한다.
   3-1. 마지막 막대의 높이를 저장한다.
   3-2. 막대의 너비를 계산한다.
   3-3. 계산된 너비 * 높이로 면적을 계산한다.
4. 계산된 면적 중 가장 큰 면적을 반환한다.

😎풀이

function largestRectangleArea(heights: number[]): number {
    const stack = [];
    let maxArea = 0;
    const n = heights.length;
    
    // 모든 막대를 순회 (마지막에 0을 추가하여 남은 계산 처리)
    for (let i = 0; i <= n; i++) {
        const h = i === n ? 0 : heights[i];
        
        // 스택이 비어있지 않고, 현재 높이가 스택의 top에 있는 막대의 높이보다 작은 경우
        while (stack.length > 0 && h < 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;
}