题解 | #最大正方形#
最大正方形
http://www.nowcoder.com/practice/0058c4092cec44c2975e38223f10470e
题目描述
给定一个由'0'和'1'组成的2维矩阵，返回该矩阵中最大的由'1'组成的正方形的面积
首先注意到一点，题目中所要求的一个正方形的面积，长方形是不符合题目要求的。
方法一：暴力枚举
思路分析
很通俗很暴力的一种解法。
整体思路为遍历给定的矩形中所有的正方形，依次求出全是 ‘1’ 的正方形的面积，然后找出最大面积即可。
再具体一点，就是从左到右，从上到下依次遍历矩形中的每个点，然后以遍历到的点为正方形的左上角，求出这个点的最大正方形的面积，以此记录下来，最后求出最大面积即可。
确定了一个点为正方形的右上角之后，在找最大正方形的过程中。这里的做法是先找他的最大边长为多少，再来一步一步扩大到最大边长这个位置，看看到最大边长这个位置是否能够组成一个全为 ‘1’ 组成的正方形。并不一定最大的边长就一定能够组成全为 ‘1’ 的正方形了，这种情况可以看下图示例。
如果以当前点为正方形的左上角，扩充不出来正方形，那么此时最大的正方形就是当前点本身，即最大面积为 1 。
具体流程参照下面代码示例：
代码示例
import java.util.*;
public class Solution {
/**
* 最大正方形
* @param matrix char字符型二维数组
* @return int整型
*/
public int solve (char[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return -1;
}
int maxArea = 0;
int rows = matrix.length;
int cols = matrix[0].length;
// 遍历每个值为 1 的点， 找出所有的可能情况
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
// 以当前点为正方形的左上角
if (matrix[i][j] == '1') {
// 往右边能够扩张到哪个位置；遇到 0 就提前结束循环。
int colSide = 0;
for (int k = j + 1; k < cols; k++) {
if (matrix[i][k] == '1') {
colSide++;
} else {
break;
}
}
// 往下边能够扩张到哪个位置；遇到 0 就提前结束循环。
int rowSide = 0;
for (int k = i + 1; k < rows; k++) {
if (matrix[k][j] == '1') {
rowSide++;
} else {
break;
}
}
// 能够扩张到的位置，最大的就是以上2者之间的最小值
int side = Math.min(rowSide, colSide);
// 只是最大情况是side， 到side时可能不符合正方形。 具体情况还要一圈一圈检查
for (int k = 1; k <= side; k++) {
if (isAllOne(matrix, i, j, i + k, j + k)) {
maxArea = Math.max(maxArea, (k + 1) * (k + 1));
}
}
// 如果最或 maxArea 的值还是 0， 则最大正方形就是当前值为 1 的小方块
if (maxArea == 0) {
maxArea = 1;
}
}
}
}
return maxArea;
}
/**
* 检查以 matrix[r1][c1] 为正方形的左上角， matrix[r2][c2] 为正方形的右下角； 是否符合正方形的条件
*/
private boolean isAllOne(char[][] matrix, int r1, int c1, int r2, int c2) {
for (int i = r1; i <= r2; i++) {
for (int j = c1; j <= c2; j++) {
if (matrix[i][j] == '0') {
return false;
}
}
}
return true;
}
} 复杂度分析
时间复杂度：O(N^5)
整个代码的流程中，有很多个嵌套的 for 循环。
首先有个遍历整个 matrix 矩形的双重 for 循环，这里是个二次方级别；
在遍历的过程中，在检查以当前点为正方形的左上角的时候，有个循环边长长度次数的检查是否满足正方形条件的循环，此时复杂度增加到了三次方级别；
在循环边长长度次数的循环中，检查是否满足正方形的步骤又是一个遍历这个“正方形”的操作，即这里又是一个双重 for 循环，此时复杂度就增加到了五次方的级别。
所以，最后的时间复杂度为 O(N^5)。
空间复杂度：O(1)
整个过程中，没有创建和数据规模 N 相关的空间，只是用有限的几个变量来记录一些必要的操作数据结果而已。而已，最后的空间的复杂度为 O(1)。
方法二：依然是暴力枚举
解题思路
在方法一的基础上，可以进行一些适当的优化，但本质还是属于暴力枚举的方法。
仍然是依次遍历每一个点，找出以每一个点为正方形的左上角时的面积是多少，再找出这里面最大的即可。区别就是在找正方形的这个过程中。
方法一是向右向下都扩充完成后再来找正方形，这里找正方形仍然要一个双重循环来遍历，时间开销是比较大的。
这里就首先以当前行向右扩充找向右扩充到的边长，在去到下一行，再向右扩充，找此时向右扩充到的边长。在这个过程中记录下向右扩充到的最小边长，以及向下扩充到的边长。取他们的最小值，就是此时正方形的边长。
需要注意的是结算正方形面积的时机，应该在每一行一行的扩充结束时结算面积，而不应该是一个大的起始点遍历完时结算面积。原因可以看下面这个情况：
当以行为单位扩充时，走到了 matrix[9][2] 这里，向右扩充的最小边长才只是 2，这样算出来的面积很明显是不符合我们想要的结果的。所以应该在每一行向右扩充完成时，就结算下此时正方形的面积。
详细过程请参看下面的代码示例。
代码示例
import java.util.*;
public class Solution {
/**
* 最大正方形
* @param matrix char字符型二维数组
* @return int整型
*/
public int solve (char[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return -1;
}
int rows = matrix.length;
int cols = matrix[0].length;
int maxArea = 0;
// 遍历每一个点，分别往右/往下扩充，看以这个点为起始的最大正方形的面积是多少
for (int startRow = 0; startRow < rows; startRow++) {
for (int startCol = 0; startCol < cols; startCol++) {
// 起始点值为 1， 才能够扩充出来正方形
if (matrix[startRow][startCol] == '1') {
// 向右扩充的边长
int toRightSideMin = Integer.MAX_VALUE;
// 向下扩充的边长。
// 为方便代码书写，这里初始为0。首先以当前行向右扩充一定会进入下面的 if 语句，使其最小值也为 1。
int toDownSide = 0;
// 以当前行，向右扩充。 然后再来到下一行，向右扩充。
// 在扩充的同时，也缩小范围，最后求出以当前起始点的最大正方形的边长，然后算出面积
for (int curRow = startRow; curRow < rows; curRow++) {
// 以行为单位，向右扩充
if (matrix[curRow][startCol] == '1') {
toDownSide++;
// 在行里面，向右扩充到多少
int toRightSide = 0;
for (int curCol = startCol; curCol < cols; curCol++) {
if (matrix[curRow][curCol] == '1') {
toRightSide++;
} else {
// 在行里面，遇到不是 1 的，就必定不满足正方形，退出循环。
break;
}
}
// 更新向右扩充的边长
toRightSideMin = Math.min(toRightSideMin, toRightSide);
int side = Math.min(toRightSideMin, toDownSide);
// 需要注意的是，每一次以行为单位遍历扩充的时候，都要结算一次面积。
// 而不能以一个起始点扩充完成之后再结算面积。
// 具体原因或者说具体情况可以参考思路里的图示。
maxArea = Math.max(maxArea, side * side);
} else if (matrix[curRow][startCol] == '0' || curRow - startRow + 1 > toRightSideMin) {
// 在以行为单位的过程中，遇到不是 1 的，就必定不满足正方形，退出循环。
// 或者往下扩充的边长，超过了往右扩充的边长，也没有必要继续往下扩充了。
break;
}
}
}
}
}
return maxArea;
}
} 复杂度分析
时间复杂度：O(N^4)
首先需要遍历每一个点为起始点找正方形的面积，这里遍历是个双重循环，复杂度已经达到了 O(N²)；
然后在每一个点为起始点找正方形面积的过程中，需要一行一行地向右遍历，这里遍历也是个双重循环，还是嵌套在外面整体遍历的双重循环里的双重循环。
所以，最后的时间复杂度为：O(N^4)。
空间复杂度：O(1)
整个过程中，没有创建和数据规模 N 相关的空间，只是用有限的几个变量来记录一些必要的操作数据结果而已。所以，最后的空间的复杂度为 O(1)。
方法三： 动态规划
思路分析
上面我们是对每个点的都暴力求出了其最大正方形的边长及面积是多少。我们可以尝试对此过程进行一些优化，主要思路是用动态规划的方式，用空间换时间的想法，对于之前求过的，已经知道的一些条件就不重复进行求算了。
大体思路是：生成一个同 matrix 同大小的 dp 矩阵。
相应的点 dp[i][j] 代表的是以 matrix[i][j] 为最大正方形的右下角，此时最大正方形的边长是多少。
对于第一行第一列的点，dp 矩阵的相应位置比较好生成： 如果当前点为 1，则 dp 矩阵上相应位置的值也为 1 。 因为只有一行或一列，最大正方形也只能是他本身，即最大边长也就只能是 1 。
比较复杂点的是 dp 矩阵中其他位置的值。
想个情形，如果当前点扩充成功了，那么和他相邻的点：他的上边、左边、左上边的点至少都需要为 1，至于最大能扩充到边长为多少，就看和他相邻的点的最大边长为多少，（而这些信息都是在之前遍历的过程中已经生成的，即是已知的，直接拿来用即可。）取他们最大边长的最小值，再加上当前这个点扩大了 1 个边长值，就是最后的最大边长值，也就是最后的 dp[i][j] 值了。
对于为什么取他相连的点的最小值而不是最大值，因为如果取最大值的话，可能这个范围里包含的值是有为 0 的，即不符合题目的正方形要求，具体情况可以参照下面的图示来想想。
以上流程，对应的代码如下：
代码示例
import java.util.*;
public class Solution {
/**
* 最大正方形
* @param matrix char字符型二维数组
* @return int整型
*/
public int solve (char[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return -1;
}
int rows = matrix.length;
int cols = matrix[0].length;
// dp[i][j] 的值代表的是： 以 matrix[i][j] 为正方形的右下角， 该正方形的最大边长
int[][] dp = new int[rows][cols];
// 最大的边
int maxSide = 0;
// 初始化 dp 矩阵的第一列
for (int i = 0; i < rows; i++) {
// 如果当前点为 1 ，那么最大正方形就是他本身，最大边长也就是 1
dp[i][0] = matrix[i][0] == '1' ? 1 : 0;
}
// 初始化 dp 矩阵的第一行
for (int j = 0; j < cols; j++) {
// 如果当前点为 1 ，那么最大正方形就是他本身，最大边长也就是 1
dp[0][j] = matrix[0][j] == '1' ? 1 : 0;
}
// 遍历所有点，填充 dp 矩阵的所有位置。
for (int i = 1; i < rows; i++) {
for (int j = 1; j < cols; j++) {
// 只有当值为 1 时，找他的边长才有意义
if (matrix[i][j] == '1') {
// 找 matrix[i][j] 为正方形的右下角， 该正方形的最大边长。
// 等号右边的意义参考图示
dp[i][j] = Math.min(
Math.min(dp[i - 1][j], dp[i][j - 1]),
dp[i - 1][j - 1])
+ 1;
// 记录最大边长
maxSide = Math.max(maxSide, dp[i][j]);
}
}
}
return maxSide * maxSide;
}
} 复杂度分析
时间复杂度：O(N²)
放眼整个代码流程中，主要的时间消耗在遍历 matrix 矩阵上，而matrix 是一个二维矩阵，遍历进行也是双重循环进行遍历。虽然之前有遍历第一行第一列的循环，但主要性能消耗还是在这个双重循环遍历上。所以，时间复杂度为 O(N²) 。
空间复杂度：O(N)
空间开辟主要是在这个 dp 矩阵上，而 dp 矩阵所占的大小和 matrix 矩阵所占的大小是一样的，其他的都是一些有限的几个变量而已。所以，空间复杂度为：O(N)。
