[LeetCode 85] Maximal Rectangle

Problem Link

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.

Example 1

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6

Example 2

Input: matrix = [["0"]]
Output: 0

Example 3

Input: matrix = [["1"]]
Output: 1

Solution

시도

• 이 문제는 전에 정리해 둔 적 있었던 직사각형 넓이를 구하는 문제와 유사했다.

  • 4중 for 문으로 직사각형의 크기를 정의해 놓고, positive() 함수로 보내 모든 점이 양수인지를 확인하여 조건을 만족한다면 최대 넓이를 업데이트하는 방식으로 풀이했었다.

    • [코드트리] 양수 직사각형의 크기 합 풀이

• 마찬가지로 모든 점이 '1'인지를 확인하는 check 함수를 작성하였고, 조건을 만족하는지를 확인하는 방식으로 풀이했다.

  • 한 가지 달랐던 점은 위 문제에서는 가로, 세로 m과 n의 범위가 1 ≤ n, m ≤ 20였으나, 이번 문제는 200이 최대였다는 점이었다.

  • 따라서 $O(n^2 * m^2)$의 시간 복잡도를 계산하면 $16*10^8 \approx 10^9$에 가까운 값이므로 time complexity를 만족할 수 없다.

소스 코드

class Solution:  # Time attack
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        n, m = len(matrix), len(matrix[0])

        def check(x1, y1, x2, y2):
            return all([
                matrix[i][j] == '1'  # str not int
                for i in range(x1, x2+1)
                for j in range(y1, y2+1)
            ])  # True or False
        
        answer = 0
        for i in range(n):
            for j in range(m):
                for k in range(i, n):
                    for l in range(j, m):
                        if check(i, j, k, l):
                            answer = max(answer, (k-i+1)*(l-j+1))
        
        return answer

회고

• LeetCode 고수들이 풀이한 방법은 histogram method라는 방식이었다.

  • 위에서부터 row 단위로 훑어, '1'이 적힌 index의 histogram 높이를 하나씩 증가시킨다.

    • m+1 길이를 갖는 heights 배열에 기록한다.

  • 그리고 heights 배열을 다시 훑어 stack에 index를 추가해준다.

    • 이 때 stack은 현재 index의 bar 높이와 이전(stack에 쌓인) index의 bar를 비교하여 cutting 작업을 도와주는 역할을 한다.

• 첫 번째 예제를 통해 살펴보자.

  • 전체 matrix에서 row를 지나갈 때마다 업데이트되는 heights 배열은 다음과 같다.

    1. [1, 0, 1, 0, 0][0]

       # #

    2. [2, 0, 2, 1, 1][0]

       # #
       # ###

    3. [3, 1, 3, 2, 2][0]

       # #
       # ###
       #####

    4. [4, 0, 0, 3, 0][0]

       #
       # #
       # #
       # #

• stack을 확인하며 직사각형을 cutting하는 방법은 다음과 같은 로직을 따른다.

  • 현재 index의 bar가 이전 index의 bar보다 크기가 작다면, stack의 값이 계속 더 클 동안 반복한다.

    • 그런 다음, index 차이로 width를 계산해 현재 index의 bar를 높이로 하는 직사각형 넓이를 계산하면 된다.

  • 예를 들어, heights가 [3, 1, 3, 2, 2]인 상황에서는 3, 3, 2, 4, 6, 5의 넓이가 계산된다.

    • 이 중 최대는 6이므로 답은 6으로 기록된다.

소스 코드

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

        heights = [0] * (m + 1)  # Include an extra element for easier calculation
        max_area = 0
        
        for row in matrix:
            for j in range(m):
                heights[j] = heights[j] + 1 if row[j] == '1' else 0
            
            # Calculate max area using histogram method
            stack = []  # push index
            for i in range(len(heights)):
                # while if stacked one is bigger than now one
                while stack and heights[stack[-1]] > heights[i]:
                    idx = stack.pop()
                    h = heights[idx]
                    if not stack:  # from 0 to i
                        w = i
                    else:  # from stack[-1]+1 to i
                        w = i - stack[-1] - 1
                    max_area = max(max_area, h * w)
                stack.append(i)
        
        return max_area