[LeetCode] 85. Maximal Rectangle

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 6.

思路: 參考 https://www.youtube.com/watch?v=g8bSdXCG-lA

1. 計算每列的值
2. 把每列的值 看成直方圖, 計算每張圖的最大值
3. 傳回所有圖 裏頭最大的值

 
class Solution(object):
    def maximalRectangle(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        global res
        res = 0
        if matrix == [] : return res
        check = [0] * len(matrix[0])
        m, n = len(matrix), len(matrix[0])
       
        # check max rectangle area
        def CalcMaxRectangle(check):
            global res
            cont, tempC = 0, []
            for i in range(len(check)):
                if check[i] == 0 or i == len(check)-1:
                    # calc maxRectangle area                               
                    if i == len(check)-1 and check[i] != 0:
                        tempC = check[i-cont:]
                    elif i - cont != i:
                        tempC = check[i-cont:i]
                       
                    temp2, tempSize = 0, len(tempC)
                   
                    for j in range(tempSize):
                        for k in range(j+1,tempSize + 1):
                             temp2 = min(tempC[j:k]) * len(tempC[j:k])
                             if temp2 > res: res = temp2
                    cont = 0
                else:
                    cont += 1

        # sweep matrix
        for i in range(m):
            for j in range(n):
                if    matrix[i][j] == "0": check[j] = 0
                else: check[j] = int(matrix[i][j]) + int(check[j])
                   
            CalcMaxRectangle(check)
       
        # return result
        return res