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