LeetCode_动态规划_中等_221.最大正方形

男娘i 2023-10-06 22:44 9阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

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

**示例 1：**  
![在这里插入图片描述][067ebc31d2ab4959bc70ff7fa1127c4e.png]  
输入：matrix = \[\[“1”,“0”,“1”,“0”,“0”\],\[“1”,“0”,“1”,“1”,“1”\],\[“1”,“1”,“1”,“1”,“1”\],\[“1”,“0”,“0”,“1”,“0”\]\]  
输出：4

**示例 2：**  
![在这里插入图片描述][a62a2bcde47d4e04a0fc078276161e61.png]  
输入：matrix = \[\[“0”,“1”\],\[“1”,“0”\]\]  
输出：1

**示例 3：**  
输入：matrix = \[\[“0”\]\]  
输出：0

**提示：**  
m == matrix.length  
n == matrix\[i\].length  
1 <= m, n <= 300  
matrix\[i\]\[j\] 为 ‘0’ 或 ‘1’

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/maximal-square

## 2.思路 ##

（1）暴力穷举法  
如果使用暴力穷举法，常见做法就是从正方形的**最大边长 Math.min(m, n)** 开始，使用 3 层 for 循环穷举即可。但是该算法时间复杂度较高，在 LeetCode 中提交时会出现超出时间限制的提示！

（2）动态规划  
思路参考[本题官方题解][Link 1]。

相关题目：  
[LeetCode\_动态规划\_中等\_1277.统计全为 1 的正方形子矩阵][LeetCode_1277._ 1]

## 3.代码实现（Java） ##

//思路1————暴力穷举法
    class Solution {
        
        public int maximalSquare(char[][] matrix) {
        
            int m = matrix.length;
            int n = matrix[0].length;
            //正方形的最大边长为 Math.min(m, n)
            int edge = Math.min(m, n);
            //从边长为 edge 的正方形开始穷举
            for (int i = edge; i >= 1; i--) {
        
            	//遍历边长为 i 的正方形在 matrix 中的所有位置
                for (int j = i; j <= m; j++) {
        
                    for (int k = i; k <= n; k++) {
        
                        if (isSquare(matrix, j - i, k - i, j - 1, k - 1)) {
        
                            //找到只包含 '1' 的最大正方形，其边长为 i，直接返回其面积即可
                            return i * i;
                        }
                    }
                }
            }
            return 0;
        }
    
        //判断 matrix 中左上角顶点坐标为(x1, y1)、右下角顶点坐标为(x2, y2)的正方形是否只包含 ‘1’
        public boolean isSquare(char[][] matrix, int x1, int y1, int x2, int y2) {
        
            for (int i = x1; i <= x2; i++) {
        
                for (int j = y1; j <= y2; j++) {
        
                    if (matrix[i][j] == '0') {
        
                        return false;
                    }
                }
            }
            return true;
        }
    }

//思路2————动态规划
    class Solution {
        
    	public int maximalSquare(char[][] matrix) {
        
    	    int m = matrix.length;
    	    int n = matrix[0].length;
    	    //dp[i][j]: 表示以 (i, j) 为右下角，且只包含 1 的正方形的边长最大值
    	    int[][] dp = new int[m][n];
    	    //正方形的最大边长，初始值为 0
    	    int maxSide = 0;
    	    for (int i = 0; i < m; i++) {
        
    	        for (int j = 0; j < n; j++) {
        
    	            if (matrix[i][j] == '1') {
        
    	                if (i == 0 || j == 0) {
        
    	                    dp[i][j] = 1;
    	                } else {
        
    	                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
    	                }
    	                //更新 maxSide
    	                maxSide = Math.max(maxSide, dp[i][j]);
    	            }
    	            //如果 matrix[i][j] == '0'，则当前位置不可能在由 1 组成的正方形中，所以 dp[i][j] = 0，即 dp 数组初始的默认值
    	        }
    	    }	
    	    return maxSide * maxSide;
    	}
    }

[067ebc31d2ab4959bc70ff7fa1127c4e.png]: https://img-blog.csdnimg.cn/067ebc31d2ab4959bc70ff7fa1127c4e.png
[a62a2bcde47d4e04a0fc078276161e61.png]: https://img-blog.csdnimg.cn/a62a2bcde47d4e04a0fc078276161e61.png
[Link 1]: https://leetcode.cn/problems/maximal-square/solution/zui-da-zheng-fang-xing-by-leetcode-solution/
[LeetCode_1277._ 1]: https://blog.csdn.net/weixin_43004044/article/details/124861488