LeetCode 221 - Maximal Square

作者 QIFAN 日期 2017-01-10
LeetCode 221 - Maximal Square

原题链接: 221. Maximal Square


题干

给定一个只含 0 和 1 的 m * n 矩阵,求该矩阵只有 1 组成的正方形的最大面积。

思路

  1. 先考虑 1 * 1 的矩阵:
    • case 1 : matrix[0][0] = 1 ,返回 1
    • case 2 : matrix[0][0] = 0 ,返回 0
  2. 2 * 2 的矩阵。只有当 4 个元素全为 1 时,即返回 2
  3. n * n 的矩阵,只有当 maxtrix[n - 1][n - 1] = 1 且 它左上方向的三个点所能构成的最大正方形边长都是 n - 1 ,才能返回 n 。
    动态计算

再概括一些,就是以点 (i, j) 为右下角,能够组成的最大正方形,取决于其左上三个相邻点所能组成的最大正方形。
动态计算 2

动态公式为:
dp[row][col] = Math.min(Math.min(dp[row][col - 1] , res[row- 1][col - 1]), res[row - 1][col]) + 1

代码:

public int maximalSquare(char[][] matrix) {
if(matrix.length == 0) {
return 0;
}
int M = matrix.length, N = matrix[0].length;
int maxSideLength = 0;
int[][] res = new int[M + 1][N + 1];
for (int row = 1 ; row <= M; row++) {
for (int col = 1; col <= N; col++) {
if(matrix[row - 1][col - 1] == '1') {
res[row][col] = Math.min(Math.min(res[row][col - 1] , res[row- 1][col - 1]), res[row - 1][col]) + 1;
maxSideLength = Math.max(res[row][col], maxSideLength); // update maxSideLength
}
}
}
return maxSideLength * maxSideLength;
}