[LeetCode/Python] Maximal Rectangle

📌문제 탐색하기

• 0과 1로 채워진 이진 이차원 행렬 형태 matrix
• 오로지 1만 포함하는 가장 큰 직사각형을 찾아 넓이 구하기

매개변수

•  n x m 크기의 바이너리 값으로 이루어진 2차원 리스트 matrix
  • 1 ≤ n, m ≤ 200

반환값

• 주어진 matrix에서 1로 이루어진 가장 큰 직사각형의 넓이를 반환

풀이 방법 생각해보기

주어진 matrix에서 각 열의 값이 누적된 높이라고 생각할 수 있다. 즉, 한 행씩 탐색하면서 각 열의 값이 1이면 이전까지 쌓인 높이에 1을 누적시키고, 0이라면 해당 열의 높이를 초기화해서 각 행을 히스토그램처럼 표현할 수 있다. 결국 이 문제는 각 행을 히스토그램으로 변환하여 가장 큰 직사각형을 구하는 방식으로 해결할 수 있다. 

 

📌코드 설계하기

1. 각 열마다의 최대 높이를 저장할 배열 heights를 생성해 모든 요소를 0으로 초기화한다.
2. 현재까지의 최대 크기 직사각형 넓이를 저장할 변수 max_area를 생성해 0으로 초기화한다.
3. matrix의 각 행을 한 줄씩 탐색하며 아래 과정을 반복한다.
   1. 해당 행을 한 칸씩 탐색하며 값이 1이면 height, 해당 열의 높이를 갱신한다. 값이 0이면 해당 열의 높이를 0으로 초기화한다.
   2. 모든 칸에 대한 탐색이 끝나면 최대 넓이를 구하기 위해 stack 리스트를 생성해 초기 인덱스 -1를 삽입한다.
   3. 각 열의 인덱스를 처음부터 끝까지 탐색하며, 현재 높이가 이전보다 낮아지는 동안 스택에서 인덱스를 꺼내 높이를 저장한다. 그리고 현재 인덱스와 스택의 최상단에 위치한 인덱스 사이의 거리를 너비로 저장해 최대 면적을 갱신한다. 모든 비교가 끝나면 스택에 현재 인덱스를 삽입 후 다음 인덱스로 넘어간다.
4. max_area를 반환한다.

 

📌정답 코드

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

        n_cols = len(matrix[0])
        heights = [0] * (n_cols + 1)

        max_area = 0

        for row in matrix:
            for col in range(n_cols):
                heights[col] = heights[col] + 1 if row[col] == "1" else 0

            stack = [-1]

            for i in range(n_cols + 1):
                while heights[i] < heights[stack[-1]]:
                    h = heights[stack.pop()]
                    w = i - stack[-1] - 1
                    max_area = max(max_area, h * w)
                stack.append(i)

        return max_area