題目

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.

思路

對(duì)于一個(gè)由１構(gòu)成的子矩陣，除去它的最右邊一列以及最下邊一行后還是由１構(gòu)成的子矩陣，因此可使用填表的方法求解，表中的元素表示以當(dāng)前格為右下元素所能形成的最大子矩陣的行數(shù)。
填表時(shí)，從做到右，從上至下掃描數(shù)組。如果當(dāng)前元素是１并且它的左上角元素也是１的話，那么有可能構(gòu)成一個(gè)更大的子矩陣。此時(shí)，按步長(zhǎng)從０到左上元素所能形成的最大子矩陣的長(zhǎng)度不斷地檢查當(dāng)前元素的上面和左面的元素是否為１，每當(dāng)左邊和上邊相隔步長(zhǎng)的元素都為１則將當(dāng)前元素對(duì)應(yīng)的表中元素+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