7月24日：最大正方形
题目如下：
如图题目所示是求一个矩阵中最大正方形面积的最大值。这让我想到了前些天刚做的求一片区域中所有海岛数量的题目，那道题是将问题转换成图搜索问题，用dfs（深度优先遍历法）来遍历图从而寻找出图中所有的海岛数量。所以我一开始也是尝试将这个问题转换成图搜索问题，可是找不到解决方法，然后就想到暴力法。
暴力法
由于正方形的面积等于边长的平方，因此要找到最大正方形的面积，首先需要找到最大正方形的边长，然后计算最大边长的平方即可。
暴力法是最简单直观的做法，具体做法如下：
遍历矩阵中的每个元素，每次遇到 1，则将该元素作为正方形的左上角；
确定正方形的左上角后，根据左上角所在的行和列计算可能的最大正方形的边长（正方形的范围不能超出矩阵的行数和列数），在该边长范围内寻找只包含 1 的最大正方形；
每次在下方新增一行以及在右方新增一列，判断新增的行和列是否满足所有元素都是 1。
class Solution {
public int maximalSquare(char[][] matrix) {
int maxSide = 0;
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return maxSide;
}
int rows = matrix.length, columns = matrix[0].length;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
if (matrix[i][j] == '1') {
// 遇到一个 1 作为正方形的左上角
maxSide = Math.max(maxSide, 1);
// 计算可能的最大正方形边长
int currentMaxSide = Math.min(rows - i, columns - j);
for (int k = 1; k < currentMaxSide; k++) {
// 判断新增的一行一列是否均为 1
boolean flag = true;
if (matrix[i + k][j + k] == '0') {
break;
}
for (int m = 0; m < k; m++) {
if (matrix[i + k][j + m] == '0' || matrix[i + m][j + k] == '0') {
flag = false;
break;
}
}
if (flag) {
maxSide = Math.max(maxSide, k + 1);
} else {
break;
}
}
}
}
}
int maxSquare = maxSide * maxSide;
return maxSquare;
}
}
看着暴力法确实很麻烦，让人看了就不想用。
那有没有啥子好点的方法呢？看到求最大让你想起了啥？对！就是动态规划。
动态规划解法
动态规划的重点是找到状态转移方程。
下面是我的动态规划解法代码：
class Solution {
public int maximalSquare(char[][] matrix) {
int row = matrix.length;
if(row==0)return 0;
int col = matrix[0].length;
if(col==0)return 0;
int[][] dp = new int[row][col];
int result = 0;
for(int i=0;i<row;i++){
if(matrix[i][0]=='0')
dp[i][0]=0;
else
dp[i][0]=1;
result = Math.max(result,dp[i][0]);
}
for(int i=0;i<col;i++){
if(matrix[0][i]=='0')
dp[0][i]=0;
else
dp[0][i]=1;
result = Math.max(result,dp[0][i]);
}
for(int i=1;i<row;i++){
for(int j=1;j<col;j++){
if(matrix[i][j]=='1'){
dp[i][j]=Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;
result = Math.max(result,dp[i][j]);
}
}
}
return result*result;
}
}