题目
最大正方形在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
示例 1：
输入：matrix = [ ["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"] ] 输出：4
示例 2：
输入：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'
题解
解题分析
解题思路
- 本题是以典型的动态规划问题；
- dp[i][j]表示以第i行第j列为右下角所能构成的最大正方形边长, 则递推式为:
dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]);
然后通过 max * max 获取矩形区域最大值。
3. 解题代码如下所示：
复杂度
时间复杂度： O(M * N)
空间复杂度： O(M * N)
解题代码
题解代码如下（代码中有详细的注释说明）：
class Solution { public int maximalSquare(char[][] matrix) { /** dp[i][j]表示以第i行第j列为右下角所能构成的最大正方形边长, 则递推式为: dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]); **/ int m = matrix.length; if(m < 1) return 0; int n = matrix[0].length; int max = 0; int[][] dp = new int[m+1][n+1]; for(int i = 1; i <= m; ++i) { for(int j = 1; j <= n; ++j) { if(matrix[i-1][j-1] == '1') { dp[i][j] = 1 + Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])); max = Math.max(max, dp[i][j]); } } } return max*max; } }
提交后反馈结果（由于该题目没有进行优化，性能一般）：
