「力扣」第 221 题:最大正方形(中等)


「力扣」第 221 题:最大正方形(中等)

在一个由 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[i][j]matrix[i][j] 为右下角的正方形的最大边长;
  • 「状态转移方程」见代码。

Java 代码 1:(不推荐的写法,直接看 Java 代码 2)

public class Solution {

    // 不使用哨兵的写法

    public int maximalSquare(char[][] matrix) {
        int rows = matrix.length;
        if (rows == 0) {
            return 0;
        }

        int cols = matrix[0].length;
        if (cols == 0) {
            return 0;
        }

        int maxSide = 0;
        int[][] dp = new int[rows][cols];
        // 先填第 1 行
        for (int j = 0; j < cols; j++) {
            if (matrix[0][j] == '1') {
                dp[0][j] = 1;
                maxSide = 1;
            }
        }

        // 再填第 1 列
        for (int i = 1; i < rows; i++) {
            if (matrix[i][0] == '1') {
                dp[i][0] = 1;
                maxSide = 1;
            }
        }

        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < cols; 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;
                    maxSide = Math.max(maxSide, dp[i][j]);
                }
            }
        }
        return maxSide * maxSide;
    }
}

复杂度分析

  • 时间复杂度:$O(MN)$,其中 $M$ 和 $N$ 是矩阵的行数和列数;
  • 空间复杂度:$O(MN)$。

注意:多设置一行,多设置一列,这样不用讨论特殊情况。

Java 代码 2:多设置一行、一列,减少讨论

public class Solution {

    public int maximalSquare(char[][] matrix) {
        int rows = matrix.length;
        if (rows == 0) {
            return 0;
        }

        int cols = matrix[0].length;
        if (cols == 0) {
            return 0;
        }


        int[][] dp = new int[rows + 1][cols + 1];

        int res = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {

                // 注意:是字符 1
                if (matrix[i][j] == '1') {
                    dp[i + 1][j + 1] = Math.min(dp[i][j], Math.min(dp[i + 1][j], dp[i][j + 1])) + 1;
                    res = Math.max(res, dp[i + 1][j + 1]);
                }

            }
        }
        return res * res;
    }
}

Java 代码 3:

  • 重复使用了之前使用过的行和列;
  • 状态多一个单位的偏移,这样不用讨论特殊情况。
public class Solution {

    public int maximalSquare(char[][] matrix) {
        int rows = matrix.length;
        if (rows == 0) {
            return 0;
        }

        int cols = matrix[0].length;
        if (cols == 0) {
            return 0;
        }

        int[] dp = new int[cols + 1];
        int res = 0;
        int leftUp = 0;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                // 把下一个需要的状态值保存起来
                int nextLeftUp = dp[j + 1];
                // 注意:是字符 1
                if (matrix[i][j] == '1') {
                    dp[j + 1] = Math.min(leftUp, Math.min(dp[j], dp[j + 1])) + 1;
                    res = Math.max(res, dp[j + 1]);
                } else {
                    // 注意:这里要重置一下
                    dp[j + 1] = 0;
                }
                leftUp = nextLeftUp;
            }
        }
        return res * res;
    }
}

(本节完)


文章作者: liweiwei419
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 liweiwei419 !
评论
 上一篇
「力扣」第 410 题:分割数组的最大值(困难) 「力扣」第 410 题:分割数组的最大值(困难)
「力扣」第 410 题:分割数组的最大值(困难) 链接:https://leetcode-cn.com/problems/split-array-largest-sum 题解:https://leetcode-cn.com/problems
下一篇 
「力扣」第 993 题:二叉树的堂兄弟节点 「力扣」第 993 题:二叉树的堂兄弟节点
「力扣」第 993 题:二叉树的堂兄弟节点 链接:993. 二叉树的堂兄弟节点; 题解链接:深度优先遍历、广度优先遍历。 在二叉树中,根节点位于深度 0 处,每个深度为 k 的节点的子节点位于深度 k + 1 处。 如果二叉树的两个节点
  目录