[leetcode] 85. Maximal Rectangle

문제 설명

링크
1과 0으로 이루어진 보드에서 1로 만들 수 있는 가장 큰 사각형의 넓이를 구하는 문제

접근 - BF

• 각 위치에서 세로 확인
• 넓이 업데이트
• 시간이 많이 소요됨

코드

    def square(self, matrix, i, j, w):
        ans = 0
        if matrix[i][j] == '1':
            if j < len(matrix[0]) - 1: 
                ans = max(ans, self.square(matrix, i, j + 1, w + 1)) # 가로 확인
            #세로 확인
            h = 0
            for y in range(i, len(matrix)):
                if matrix[y][j - w : j + 1] == ['1'] * (w + 1): h += 1
                else: break
            # print(h,w, i, j, ">> h,w, i, j")
            ans = max(ans, (w + 1) * h)
        return ans
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        ans = 0
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                ans = max(ans, self.square(matrix, i, j, 0))
        return ans

접근 2 - Histogram

-참고 문제 , velog

• 각 행에서 1 들을 높이로 생각
• [[1, 0, 0, 1, 0],
  [1, 0, 0, 1, 0]] 의 경우 높이 2 인 histogram
  
• 행을 돌면서 histogram 문제와 마찬가지로 스택을 이용하여 최대 넓이 계산

코드 2

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if not matrix or not matrix[0]:
            return 0
        n = len(matrix[0])
        height = [0] * (n + 1)
        ans = 0
        for row in matrix:
            for i in range(n):
                height[i] = height[i] + 1 if row[i] == '1' else 0
            stack = [-1]
            for i in range(n + 1):
                while height[i] < height[stack[-1]]:
                    h = height[stack.pop()]
                    w = i - 1 - stack[-1]
                    ans = max(ans, h * w)
                stack.append(i)
        return ans