Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.
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.
Solution
dp[x][y] = min(dp[x - 1][y - 1], dp[x][y - 1], dp[x - 1][y]) + 1
上式中，dp[x][y]表示以坐标(x, y)为右下角元素的全1正方形矩阵的最大长度（宽度）
(Maximal-Square.java) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| public class Solution {
public int maximalSquare(char[][] matrix) {
if (matrix.length==0)
return 0;
int m = matrix.length;
int n = matrix[0].length;
int[][] dp = new int[m+1][n+1];
int ret = 0;
for (int i=1;i<=m;i++){
for (int j=1;j<=n;j++){
if (matrix[i-1][j-1] == '1'){
// 必须比较dp[i-1][j],dp[i][j-1],dp[i-1][j-1]否则可能出现长方形
dp[i][j] = Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
ret = Math.max(ret,dp[i][j]);
}
}
}
return ret*ret;
}
}
|
(Maximal-Square.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution(object):
def maximalSquare(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
if len(matrix) == 0:
return 0
m = len(matrix)
n = len(matrix[0])
dp = [[0]*n for x in range(m)]
ret = 0
for i in range(m):
for j in range(n):
dp[i][j] = int(matrix[i][j])
if i and j and dp[i][j]:
dp[i][j] = min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1
ret = max(ret,dp[i][j])
return ret*ret
|