[LeetCode] 85. Maximal Rectangle

해당 문제는 이전 문제와 풀이과정이 많이 비슷한것을 알 수 있는것이, 행렬 데이터를 순회하며 히스토그램 문제로 변환하여 풀이가 가능하다.

높이 데이터를 행을 순회하며 쌓아가고 그렇게 축적된 높잇값을 활용하여 히스토그램 알고리즘을 활용하여 풀이해야한다.

😎풀이

function maximalRectangle(matrix: string[][]): number {
    if (matrix.length === 0 || matrix[0].length === 0) return 0;

    const rows = matrix.length;
    const cols = matrix[0].length;
    const heights = Array(cols).fill(0);
    let maxArea = 0;

    // 각 행을 순회하면서 히스토그램 문제로 변환
    for (let i = 0; i < rows; i++) {
        // 각 열의 높이 갱신
        for (let j = 0; j < cols; j++) {
            if (matrix[i][j] === '1') {
                heights[j]++;
            } else {
                heights[j] = 0;
            }
        }
        
        // 현재 행에서의 최대 직사각형 면적 계산
        maxArea = Math.max(maxArea, largestRectangleArea(heights));
    }

    return maxArea;
}

// 히스토그램에서 가장 큰 직사각형 면적을 찾는 함수
function largestRectangleArea(heights: number[]): number {
    const stack: number[] = [];
    let maxArea = 0;
    heights.push(0); // 마지막에 0을 추가하여 모든 막대를 처리할 수 있게 함

    for (let i = 0; i < heights.length; i++) {
        while (stack.length > 0 && heights[stack[stack.length - 1]] > heights[i]) {
            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;
}