### 题目

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 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0


1


1 0
1 0


#### 代码

/** Brute Force */
public class Solution {
public int maximalSquare(char[][] matrix) {
int result = 0;
if (matrix.length == 0) { return result; }
int height = matrix.length, width = matrix[0].length;
for (int i = 0; i < height; i++) {
for (int j = 0; j < width; j++) {
int maxPossibleHeight = height -i;
if (maxPossibleHeight <= result) { return result * result; } // 剪枝
int maxPossibleWidth = width - j;
if (maxPossibleWidth <= result) { break; } // 剪枝
int range = Math.min(maxPossibleHeight,maxPossibleWidth);
result = Math.max(result,checkSquare(matrix,i,j,range));
}
}
return result * result;
}
/** Check the max size of Square start from a certain point (left-upper corner) [x,y]  */
public int checkSquare(char[][] matrix, int x, int y, int range) {
int result = 0;
for (int i = 0; i < range; i++) {
for (int j = x + i, k = y; k <= y + i; k++) { if (matrix[j][k] == '0') { return result; } }
for (int j = y + i, k = x; k <= x + i; k++) { if (matrix[k][j] == '0') { return result; } }
result++;
}
return result;
}
}


### 动态规划

0	0	0	1
1	1	0	1
1	1	1	1
0	1	1	1
0	1	1	1


1层

0


2层

0	0
1	1


3层

0	0	0
1	1	0
1	2	1


4层

0	0	0	1
1	1	0	1
1	2	1	1
0	1	2	2


5层

0	0	0	1
1	1	0	1
1	2	1	1
0	1	2	2
0	1	2	3


0|  0   0   0   0
-----------------
0|  0   0	0	1
0|  1	1	0	1
0|  1	2	1	1
0|  0	1	2	2
0|  0	1	2	3


#### 代码

public class Solution {
public int maximalSquare(char[][] matrix) {
int size = 0;
if (matrix.length == 0 || matrix[0].length == 0) { return size * size; }
int height = matrix.length, width = matrix[0].length;
int[][] dpTable = new int[height+1][width+1];
for (int i = 1; i < dpTable.length; i++) {
for (int j = 1; j < dpTable[0].length; j++) {
if (matrix[i-1][j-1] == '1') {
int dpVal = Math.min(Math.min(dpTable[i-1][j],dpTable[i][j-1]),dpTable[i-1][j-1]) + 1;
dpTable[i][j] = dpVal;
size = Math.max(size,dpVal);
}
}
}
return size * size;
}
}


### 动态规划，空间缩小至 $O(n)$

#### 代码

public class Solution {
public int maximalSquare(char[][] matrix) {
if (matrix.length == 0 || matrix[0].length == 0) { return 0; }
int max = 0, height = matrix.length, width = matrix[0].length;
int[] dpHelper = new int[width+1];
for (int i = 0; i < height; i++) {
int[] localHelper = new int[width+1];
for (int j = 0; j < width; j++) {
if (matrix[i][j] == '1') {
int dpVal = Math.min(localHelper[j],Math.min(dpHelper[j],dpHelper[j+1])) + 1;
localHelper[j+1] = dpVal;
max = Math.max(max,dpVal);
}
}
dpHelper = localHelper;
}
return max * max;
}
}