题目：最大正方形

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

示例:

来源：力扣（LeetCode）第221题

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

分析：

dp题
首先正方形的面积一定是根号后还为正数的。
首先面积为1,这很简单，只要出现了1那肯定有1。
然后是面积为4的，也就是边长为2的，如果边长为2，那么这个数组的左边，上边和左上肯定不能是0，以及自己也不能是0。
最后来看看面积是9的情况，边长为3。如果边长为3，那么同样也是左边，右边和左上，他们的值不仅要不等于0，而且每个值都至少得是2，因为他们的三个方向也依然不能是0。
所以我们每次都找这三个方向，算出他们的最小值。然后再加上1，这样就能得到这个点最大的面积了。

代码：

class Solution {
    public int maximalSquare(char[][] matrix) {
        int m = matrix.length;
        if (m == 0) return 0;
        int n = matrix[0].length;
        int[][] dp = new int[m+1][n+1];
        int ans = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (matrix[i-1][j-1] == '1') {
                    dp[i][j] = Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1])) + 1;
                    ans = Math.max(ans, dp[i][j]);
                }
            }
        }
        return ans * ans;
    }
}

然后还可以用滚动数组优化

class Solution {
public int maximalSquare(char[][] matrix) {
    int m = matrix.length;
    if (m == 0) return 0;
    int n = matrix[0].length;
    int[][] dp = new int[2][n+1];
    int ans = 0;
    for (int ii = 1; ii <= m; ii++) {
        int i = ii & 1, pi = i ^ 1;
        for (int j = 0; j <= n; j++) dp[i][j] = 0;
        for (int j = 1; j <= n; j++) {
            if (matrix[ii-1][j-1] == '1') {
                dp[i][j] = Math.min(dp[pi][j], Math.min(dp[i][j-1], dp[pi][j-1])) + 1;
                ans = Math.max(ans, dp[i][j]);
            }
        }
    }
    return ans * ans;
}
}