题目描述
Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.
1
2
3
4
5
6
7
8
| Input:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Output: 4
|
解析
题目给了一堆0和1组成的矩阵，问矩阵中由1组成的方块的最大面积
这是我本人非常喜欢的一道题目，描述得十分简洁，实现算法从暴力到DP，能够体现出计算机科学以及算法的优雅，暴力的方法非常显而易见，穷尽所有的可能性，一行一行，发现连续的1则往下继续探索，看看是否满足方阵的要求，即长宽相等，Leetcode官方题解给出的代码如下，而且居然能够AC，可见样例比较弱
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
30
31
32
33
34
| public class Solution {
public int maximalSquare(char[][] matrix) {
int rows = matrix.length, cols = rows > 0 ? matrix[0].length : 0;
int maxsqlen = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (matrix[i][j] == '1') {
int sqlen = 1;
boolean flag = true;
while (sqlen + i < rows && sqlen + j < cols && flag) {
for (int k = j; k <= sqlen + j; k++) {
if (matrix[i + sqlen][k] == '0') {
flag = false;
break;
}
}
for (int k = i; k <= sqlen + i; k++) {
if (matrix[k][j + sqlen] == '0') {
flag = false;
break;
}
}
if (flag)
sqlen++;
}
if (maxsqlen < sqlen) {
maxsqlen = sqlen;
}
}
}
}
return maxsqlen * maxsqlen;
}
}
|
不过这题还有一个更为巧妙的方法，利用dp，我们用dp[i][j]来表示以(i, j)为右下角的方阵的边长，如图：
递推公式如下：
dp(i,j)=min(dp(i,j−1),dp(i−1,j),dp(i−1,j−1))+1根据递推公式，就能够用少量代码十分优雅地解决这个问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| public int maximalSquare(char[][] matrix) {
if(matrix.length == 0)
return 0;
int res = 0;
int[][] dp = new int[matrix.length][matrix[0].length];
for(int i = 0; i < matrix.length; i++){
for(int j = 0; j < matrix[0].length; j++){
if(matrix[i][j] == '1'){
int left = i - 1 > -1 ? dp[i - 1][j] : 0;
int up = j - 1 > - 1 ? dp[i][j - 1] : 0;
int dig = i - 1 > - 1 && j - 1 > -1 ? dp[i - 1][j - 1] : 0;
dp[i][j] = 1 + Math.min(left, Math.min(up,dig));
res = Math.max(res, dp[i][j] * dp[i][j]);
}
}
}
return res;
}
|
时间复杂度为O(mn)，空间复杂度为O(mn)，其中m、n为矩阵长宽
Follow Up
如果要找一个最大矩形的面积呢？