Maximal-Square

LeetCode

第50天。

恍恍惚惚，就50天了。

今天的题目是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
2
3
4
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,那么我们就可以继续向下扩展，这样就可以遍历出一个正方形，然后我们在对matrix进行遍历的时候还可以通过当前的最大面积来提早结束遍历：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def expend(self,matrix,i,j,ret):
    """
    :type matrix: List[List[str]]
    :type i: int
    :type j: int
    :type ret: int
    :rtype ret
    """
    if i >= len(matrix) or j >= len(matrix[0]):
        return ret
    for k in range(ret+1):
        if matrix[i][j - k] == '0' or matrix[i-k][j] == '0':
            return ret
    return self.expend(matrix,i+1,j+1,ret+1)

def maximalSquare1(self, matrix):
    """
    :type matrix: List[List[str]]
    :rtype: int
    """
    ret,i = 0,0
    while i + ret < len(matrix):
        j = 0
        while j + ret < len(matrix[0]):
            if matrix[i][j] == '1':
                ret = max(ret,self.expend(matrix,i+1,j+1,1))
            j += 1
        i += 1
    return ret*ret

挺暴力的方法，不知道是不是因为可以提前结束，所以这个方法也直接AC了。

然后是DP的解法。

在解决这个问题之前，我们先考虑如果求出以matrix[i][j]为右下角的正方形最大面积。

如果matrix[i][j] = '0',那么显然size[i][j] = 0
如果matrix[i][j] = '1',那么我们需要考虑其向上，向左，向左上的最大面积。

假设size[i-1][j-1] = 2,则我们至少可以知道：

1
2
3
4
5
[
    [1,1,*]
    [1,1,*]
    [*,*,-]
]

如果size[i][j-1] = 2,我们至少知道：

1
2
3
4
5
[
    [*,*,*]
    [1,1,*]
    [1,1,-]
]

如果size[i-1][j] = 2,我们至少知道：

1
2
3
4
5
[
    [*,1,1]
    [*,1,1]
    [*,*,-]
]

从上面可以看出来，只有当size[i-1][j-1] == 2 and size[i][j-1] == 2 and size[i-1][j-1] == 2时，size[i][j] == 3,

则我们可以得出以下递推式：

size[i][j] = min(size[i-1][j-1],size[i][j-1],size[i-1][j])+1 if matrix[i][j] == '1'
size[i][j] = 0 if matrix[i][j] == '0'

然后我们还需要考虑一下边界条件，因为当i=0或j=0时，上面的递推式是没有考虑到的，我们再加上：

size[i][j] = (matrix[i][j] == '1') where i == 0 or j == 0

然后我们就可以写出以下解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def maximalSquare(self,matrix):
    if len(matrix) == 0:
        return 0
    dp1 = []
    ret = 0
    for i in range(len(matrix[0])):
        t = int(matrix[0][i] == '1')
        dp1.append(t)
        ret = max(ret,t)
    for i in range(1,len(matrix)):
        dp2 = [ 0 for i in range(len(matrix[0])) ]
        dp2[0] = int(matrix[i][0] == '1')
        ret = max(dp2[0],ret)
        for j in range(1,len(matrix[0])):
            if matrix[i][j] == '1':
                dp2[j] = min(min(dp1[j-1],dp1[j]),dp2[j-1]) + 1
            ret = max(ret,dp2[j])
        dp1 = dp2
    return ret*ret