221、最大的正方形

leetcode

Created At : 2020-07-26 00:19

Count:895 Views 👀 :

Comment:

221、最大的正方形
1. 示例:

题解

1、动态规划
2、暴力枚举

221、最大的正方形

在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。

示例:

链接：https://leetcode-cn.com/problems/maximal-square

题解

最大正方形——最大连通正方形
暴力枚举
动态规划
- dp[i][j]表示当前位置的所在的最大的正方形的边长，它与之前的状态的关系如下：
  $$ dp(i,j) = min(dp(i - 1,j),dp(i - 1,j - 1),dp(i,j - 1)) + 1 $$

1、动态规划

public class Solution {
    public int maximalSquare(char[][] matrix) {
        int rows = matrix.length;
        int cols = rows > 0?matrix[0].length:0;// 避免出现空的矩阵出错
        // dp状态数组
        int[][] dp = new int[rows + 1][cols + 1];
        int maxsqlen = 0;// 最大矩阵的长度
        for (int i = 1;i <= rows; i++) {
            for (int j = 1;j <= cols;j++) {
                // 前对角线的是否存在正方形
                if (matrix[i - 1][j - 1] == '1') {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j],dp[i - 1][j - 1]),dp[i][j - 1])+1;
                    maxsqlen = Math.max(maxsqlen,dp[i][j]);
                }
            }
        }
        return maxsqlen * maxsqlen;
    }
}
// 空间优化
// 由于只是相邻两行有影响，所以只用一维的dp数组
public int maximalSquare(char[][] matrix) {
    int rows = matrix.length;
    int cols = rows > 0?matrix[0].length:0;// 避免出现空的矩阵出错
    // dp状态数组
    int[] dp = new int[cols + 1];
    int maxsqlen = 0;// 最大矩阵的长度
    int pre = 0;// 记录前一个j
    for (int i = 1;i <= rows; i++) {
        for (int j = 1;j <= cols;j++) {
            int tmp = dp[j];// 获取前一次扫描的dp[j]
            if (matrix[i - 1][j - 1] == '1') {
                dp[j] = Math.min(Math.min(dp[j - 1],pre),dp[j]) + 1;// 更新dp[j]
                maxsqlen = Math.max(maxsqlen,dp[j]);// 更新最大边长
            }else{
                dp[j] = 0;
            }
            // 更新前一个值
            pre = tmp;
        }
    }
    return maxsqlen * maxsqlen;
}

2、暴力枚举

遍历矩阵中的每个元素，每次遇到 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;
        // 遍历矩阵中的每个元素，每次遇到 1，则将该元素作为正方形的左上角；
        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);
                    // 每次在下方新增一行以及在右方新增一列，判断新增的行和列是否满足所有元素都是 1。
                    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;
    }
}

// 链接：https://leetcode-cn.com/problems/maximal-square/solution/zui-da-zheng-fang-xing-by-leetcode-solution/

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com