原题
在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
示例:
输入: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 输出: 4
解法
思想
动态规划：
设dp(x,y)是以matrix[x][y]为右下角的点的最大正方形的边长，则如果matrix[x][y]=='1'，那么dp(x,y)=min(dp(x-1,y-1),dp(x-1,y),dp(x,y-1))。否则dp(x,y)=0
代码
class Solution {
public int maximalSquare(char[][] matrix) {
int height = matrix.length;
if(height == 0) return 0;
int width = matrix[0].length;
int[][] edge = new int[height][width];
int maxEdge = 0;
for(int i = 0 ; i < height;i++){
for(int j = 0;j < width;j++){
if(matrix[i][j] == '0'){
edge[i][j] = 0;
continue;
}
int leftUp = (i == 0 || j == 0) ? 0 : edge[i-1][j-1];
int left = j == 0 ? 0 : edge[i][j-1];
int up = i == 0 ? 0 : edge[i-1][j];
edge[i][j] = Math.min(Math.min(leftUp,left),up) +1;
if(edge[i][j]>maxEdge) maxEdge = edge[i][j];
}
}
return maxEdge*maxEdge;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode221-%e6%9c%80%e5%a4%a7%e6%ad%a3%e6%96%b9%e5%bd%a2/
