Q221 Maximal Square

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

解题思路：

思路1：
对于一个 [2,2] 的区域，如果左上角为 1，且它的右边、下边和斜对角线的元素也为 1，则左上角的数值就可以加 1。扫描一遍矩阵后，如果发现存在 [2,2] 里还存在4个数值相等的区域，则继续扫描矩阵，直到矩阵不改变为止。最后，矩阵中最大的数就是最大面积的边长。

每次扫描矩阵结束后，矩阵的最后一行和最后一列的值都会用不到，下一次不用扫描它们。

这样，时间复杂度为 O(min(m,n) * m * n) ，其中 m 为矩阵的行，n为矩阵的列。min(m,n) 的原因就是遇到最坏情况（所有值都为1），则需要合并 min(m,n) 次。由于在原矩阵上直接修改，则空间复杂度为 O(1)。

思路2：
既然每次都是根据左上角判断，为什么不根据右下角判断呢？这样，只需要遍历一次矩阵，就可以更新所有的边长值。在更新的过程中，记录最大边长，最后求最大面积即可。

这个思路是一个动态规划的问题，右下角的元素取决于相邻的3个元素中的最小值加上当前右下角的数字的1，即：

matrix[i][j] += min(matrix[i][j-1], matrix[i-1][j], matrix[i-1][j-1])

如果右下角的数字为0，就不用更新其数值。

这样，时间复杂度为 O(m * n) ，其中 m 为矩阵的行，n为矩阵的列；由于在原矩阵上直接修改，则空间复杂度为 O(1)。

Python实现：

class Solution:
    # AC版本1：时间复杂度 O(min(m,n)*m*n)，空间复杂度 O(1)
    def maximalSquare(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        for i in range(len(matrix)): # 先将矩阵中的字符转化为数字
            for j in range(len(matrix[i])):
                matrix[i][j] = int(matrix[i][j])
        unchange = True
        k = 1 # 表示每循环一次，矩阵的大小缩小一行和一列
        while unchange:
            for i in range(len(matrix) - k):
                for j in range(len(matrix[i]) - k):
                    if matrix[i][j] != 0 and matrix[i][j] == matrix[i][j+1] == matrix[i+1][j] == matrix[i+1][j+1]:
                        matrix[i][j] += 1
                        unchange = False
            if unchange == False:
                unchange = True
                k += 1
            else:
                break
        maxlen = 0
        for li in matrix:  # matrix 中最大的值就是面积的边长 
            maxlen = max(maxlen, max(li))
        return maxlen * maxlen

    # AC版本2：时间复杂度 O(m*n)，空间复杂度 O(1)
    def maximalSquare2(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        m = len(matrix) # 矩阵的行
        if m == 0: 
            return 0
        n = len(matrix[0])  # 矩阵的列
        maxlen = 0 # 最大边长
        for i in range(m):
            for j in range(n):
                matrix[i][j] = int(matrix[i][j]) # 转化为整数
                if matrix[i][j] == 1: 
                    if i > 0 and j > 0:  # 一个 2*2 的区域，右下角依附左面、上面、左上角的3个元素
                        matrix[i][j] = min(matrix[i][j-1], matrix[i-1][j], matrix[i-1][j-1]) + 1
                maxlen = max(maxlen, matrix[i][j])
        return maxlen ** 2

a = [
['1','0','1','0','0'],
['1','0','1','1','1'],
['1','1','1','1','1'],
['1','0','1','1','1']
]
print(Solution().maximalSquare2(a)) # 9