[LeetCode 풀이/python] 85. Maximal Rectangle (hard)

문제 설명: 0 과 1 로만 채워진 rows x cols 형태의 행렬 matrix 가 주어졌을 때, 1 만 포함하는 가장 큰 직사각형을 찾고 그 넓이를 리턴하시오.

 

(Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.)

 

예시 1)

입력: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]  -->  출력: 6

설명: 최대 크기의 직사각형은 위의 그림에 표시되어 있음

 

예시 2)

입력: matrix = []  -->  출력: 0

 

예시 3)

입력: matrix = [["0"]]  -->  출력: 0

 

예시 4)

입력: matrix = [["1"]]  -->  출력: 1

 

예시 5)

입력: matrix = [["0", "0"]]  -->  출력: 0

 

제한 조건:

• rows == matrix.length
• cols == matrix.length
• 0 <= row, cols <= 200
• matrix[i][j] 의 값은 '0' 또는 '1'

 

------ * ------ * ------ * ------

 

[풀이 1안]

• 접근법
  • matrix 의 각 셀 (i, j) 을 어느 한 꼭지점으로 하는 최대 직사각형을 찾도록 backtracking 알고리즘을 쓸 수 있지 않을까 생각했으나 구체적인 구현 단계에서 막혀... discussion 을 참고함
  • 이전 [84. Largest Rectangle in Histogram] 문제의 풀이를 응용하면 이를 조금만 변형하는 것만으로 해결 가능하다는 것...!
  • matrix 의 각 행을 histogram 의 바닥(x axis) 로 보고 & 연속된 1 로 이루어진 셀을 높이로 간주하여 각 경우에 대해 최대 넓이 직사각형을 구하기
    • 예를 들어, row 0: height = [1, 0, 1, 0, 0] , row 1: height = [2, 0, 2, 1, 1] ... and so on

 

 

• 코드 구현

def maximalRectangle(matrix: List[List[str]]) -> int:
    if (not matrix) or (not matrix[0]): return 0
        
    rows, cols = len(matrix), len(matrix[0])
    ans = 0
    heights = [0] * (cols + 1)
    for row in matrix:
        stack = [-1]
        for c in range(cols):
            heights[c] = heights[c] + int(row[c]) if row[c] == "1" else 0
            
        for i in range(len(heights)):
            while heights[i] < heights[stack[-1]]:
                h = heights[stack.pop()]
                w = i - stack[-1] - 1
                ans = max(ans, h*w)
            stack.append(i)
    return ans

 

• 결과
  • m x n 행렬의 각 행에 대해 O(n) 비용이 소요되므로, 총 O(m x n) 의 시간 복잡도를 가짐
  • 세상에 똑똑한 사람 왤케 많은거야...... 따흑