221. 最大正方形

题目

在一个由 ‘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’

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximal-square
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

定义为以为正方形右下角顶点构成的最大正方形的边长。画一个图就可以推算出下面的方程：

%2C%20dp%5Bi%20-%201%5D%5Bj%20-%201%5D)%20%2B%201#card=math&code=dp%5Bi%5D%5Bj%5D%20%3D%20Math.min%28Math.min%28dp%5Bi%20-%201%5D%5Bj%5D%2C%20dp%5Bi%5D%5Bj%20-%201%5D%29%2C%20dp%5Bi%20-%201%5D%5Bj%20-%201%5D%29%20%2B%201&id=iQyt8)

代码

class Solution {
    public int maximalSquare(char[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];
        int side = 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;
                    }
                    side = Math.max(side, dp[i][j]);
                }
            }
        }
        return side * side;
    }
}