难度: 中等(Medium)

题目

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing all 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 4.

思路

对于一个由１构成的子矩阵，除去它的最右边一列以及最下边一行后还是由１构成的子矩阵，因此可使用填表的方法求解，表中的元素表示以当前格为右下元素所能形成的最大子矩阵的行数。
填表时，从做到右，从上至下扫描数组。如果当前元素是１并且它的左上角元素也是１的话，那么有可能构成一个更大的子矩阵。此时，按步长从０到左上元素所能形成的最大子矩阵的长度不断地检查当前元素的上面和左面的元素是否为１，每当左边和上边相隔步长的元素都为１则将当前元素对应的表中元素+1。最大的各种元素的平方即为所求。

题例的表格：
[1, 1, 0, 0, 0]
[1, 2, 0, 0, 0]
[0, 0, 1, 0, 0]
[0, 0, 0, 1, 1]

代码

class Solution(object):
    def maximalSquare(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        if matrix==None or len(matrix)==0:
            return 0
        dp = [[] for i in range(len(matrix))]
        cur_max = 0
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == '0':
                    dp[i].append(0)
                else:
                    dp[i].append(1)
                    if cur_max == 0:
                        cur_max = 1
                if i!=0 and j!=0 and dp[i][j]==1 and dp[i-1][j-1]!=0:
                    step = dp[i-1][j-1]
                    for k in range(1,step+1):
                        if matrix[i-k][j]=='0' or matrix[i][j-k] == '0':
                            break
                        else:
                            dp[i][j] += 1
                            if dp[i][j] > cur_max:
                                cur_max = dp[i][j]
        return cur_max ** 2