题目描述

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

示例:

输入: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

输出: 4

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

解法1

题目要求找到矩阵matrix中只包含1的最大正方形，并返回其面积。我们可以转换成求子方阵中1的数量。如果子方阵中所有元素的和与子方阵的size的平方相等，那么这个方阵中的元素肯定都是1。

如果采用暴力的解法：

• 枚举每个起始位置时间复杂度O(n^2)；
• 在该位置下枚举子方阵的大小时间复杂度O(n)；
• 最后需要统计该方阵有多少个1，时间复杂度为O(n^2)。

那么整体来看，使用暴力法的时间复杂度为O(n^5)。这么高的复杂度，肯定是通不过的。但是我们可以利用预计算，提前求出从左上角(0, 0)到任意位置的矩阵中1的数量。再通过简单的加减法，就能求得任意子方阵中1的数量：

图1描述了对于矩阵matrix，通过预计算求得从(0, 0)到任意位置(row, col)的和。我们先忽略sum这个矩阵是怎么求得的，下面我们用它实现O(1)的时间复杂度来计算任意子方阵中1的数量。

图1中红色区域是我们想要求得的解，红色 = 橙色 - 蓝色 - 绿色 + 紫色。因为从左上角到任意位置的和都通过预计算求过了，只需要带入公式用O(1)的时间复杂度就能求得起始位置为(row, col)，大小为size的方阵的和。对于整个问题，我们只需要枚举起始位置和枚举方阵的大小，整体的时间复杂度为O(n^3)。

上面的那个例子可以用公式可以表述为：

count = sum[row + size - 1][col + size - 1] - //橙色
        sum[row + size - 1][col - 1] -        // 蓝色
        sum[row - 1][col + size - 1] +        // 绿色
        sum[row - 1][col - 1];                // 紫色

那么我们怎么预计算求得(0, 0)到(row, col)的和呢？这就用到了动态规划的思想，用较小规模问题的解计算出更大规模问题的解。

图3显示为了求得(0, 0)到(row, col)的和，我们只需要3个矩阵，他们分别比要求得的矩阵长、宽、长与宽各小1个单位，再加上右下角matrx[row][col]的元素。观察图3标注白色的数字：4 + 4 – 2 + 1 -> 7，我们使用了3×2、2×3、2×2的三个矩阵求得了3×3的矩阵。

用公示可以表示为：sum[row][col] = sum[row – 1][col] + sum[row][col – 1] – sum[row – 1][col – 1] + matrix[row][col] – ‘0’。但是在实现的时候，row-1、col-1可能会发生越界，我们需要判断row和col的边界。

for (int row = 0; row < nRow; row++) {
    for (int col = 0; col < nCol; col++) {
        sum[row][col] = matrix[row][col] - '0';
        if (row != 0 && col != 0)
            sum[row][col] -= sum[row - 1][col - 1];
        if (col != 0)
            sum[row][col] += sum[row][col - 1];
        if (row != 0)
            sum[row][col] += sum[row - 1][col];
    }
}

全部代码如下，时间复杂度为O(n^3)、空间复杂度为O(n^2)：

class Solution {
    public int maximalSquare(char[][] matrix) {
        if (matrix.length == 0)
            return 0;
        int nRow = matrix.length;
        int nCol = matrix[0].length;
        int ans = 0;

        int[][] sum = new int[nRow][nCol];

        for (int row = 0; row < nRow; row++) {
            for (int col = 0; col < nCol; col++) {
                // sum[row][col] = sum[row - 1][col] + sum[row][col - 1] - sum[row - 1][col - 1] + matrix[row][col] - '0';
                sum[row][col] = matrix[row][col] - '0';
                if (row != 0 && col != 0)
                    sum[row][col] -= sum[row - 1][col - 1];
                if (col != 0)
                    sum[row][col] += sum[row][col - 1];
                if (row != 0)
                    sum[row][col] += sum[row - 1][col];
            }
        }

        for (int row = 0; row < nRow; row++) {
            for (int col = 0; col < nCol; col++) {
                for (int size = Math.min(nRow - row, nCol - col); size > 0; size--) {
//                    count = sum[row + size - 1][col + size - 1] -
//                            sum[row + size - 1][col - 1] -
//                            sum[row - 1][col + size - 1] +
//                            sum[row - 1][col - 1];
                    int count = sum[row + size - 1][col + size - 1];
                    if (col != 0 && row != 0)
                        count += sum[row - 1][col - 1];
                    if (col != 0)
                        count -= sum[row + size - 1][col - 1];
                    if (row != 0)
                        count -= sum[row - 1][col + size - 1];
                    if (count == size * size) {
                        ans = Math.max(ans, size);
                        break;
                    }
                }
            }
        }
        return ans * ans;
    }
}