85. Maximal Rectangle

[zeikar]

Problem link

https://leetcode.com/problems/maximal-rectangle/

Problem Summary

2차원 배열에서 1로만 이루어진 가장 큰 직사각형의 넓이를 구하는 문제.

Solution

정사각형의 경우 간단한 DP로 가능한데 직사각형이므로 DP 풀이는 약간 복잡하다.
예전에 로이형 유튜브에서 보긴 해서 그 풀이로 가보기로 하자.

이전 문제인 84. Largest Rectangle in Histogram 문제를 응용하면 된다. 각 칸을 히스토그램의 칸이라 생각하고 아래 행으로 갈 때마다 1이면 바의 높이가 1씩 증가하는 것으로 생각할 수 있다. 0이면 0으로 처리한다.

여기서 첫 번째 행은 그대로 10100 이지만 두 번째 행을 위로 쌓는다고 생각하면 20211, 비슷하게 31322, 40030 으로 할 수 있다. 이 높이들에 대해 84번 문제의 가장 큰 직사각형을 구하는 알고리즘을 사용하면 된다.

Source Code

from typing import List


class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if len(matrix) == 0:
            return 0

        ans = 0
        rows = len(matrix)
        cols = len(matrix[0])
        heights = [0] * (cols + 1)

        for i in range(rows):
            for j in range(cols):
                heights[j] = (heights[j] + 1) * int(matrix[i][j])

            # largest rectangle in histogram
            stack = [-1]
            for j in range(cols + 1):
                while heights[stack[-1]] > heights[j]:
                    width = j - stack[-2] - 1
                    height = heights[stack[-1]]
                    ans = max(ans, height * width)
                    stack.pop()

                stack.append(j)

        return ans