Maximal Square

Question

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area.

Example

For example, given the following matrix:

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

Return 4.

Solution

正方形可以一用一个角加边长来确定。遍历数组，以数组元素为正方形右下角，求出最大边长即可求出最大面积。

状态：square[i][j]代表以matrix[i-1][j-1]为右下角的正方形最长的边长。

转移函数：

    1. square[i][j]＝min(square[i-1][j], square[i-1][j-1], square[i][j-1])+1 
    (matrix[i-1][j-1] == 1)

    2. square[i][j]=0 (matrix[i-1][j-1] == 0)

    每个正方形的左边，上面，左上正方形最大边长决定了该正方形的最大边长

初始化：额外多创建一行和一列，并初始化为0

结果：遍历过程中每次取最大边长之积

tips: 因为每个正方形只和其左边，上面，左上正方形有关，因此可以用rolling array来进行空间优化，只用两行来记录即可，更新偶数行看奇数行，更新奇数行看偶数行。

代码如下：

public class Solution {
    /**
     * @param matrix: a matrix of 0 and 1
     * @return: an integer
     */
    public int maxSquare(int[][] matrix) {
        // write your code here
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return 0;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        //使用rolling array
        int[][] square = new int[2][n + 1];

        for(int i = 0; i < 2; i++){
            square[i][0] = 0;
        }

        for(int j = 0; j <= n; j++){
            square[0][j] = 0;
        }

        int max = 0;
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(matrix[i - 1][j - 1] == 1){
                    square[i % 2][j] = Math.min(square[i % 2][j - 1], Math.min(square[(i - 1) % 2][j - 1], square[(i - 1) % 2][j])) + 1;
                }else{
                    square[i % 2][j] = 0;
                }
                max = Math.max(max, square[i % 2][j] * square[i % 2][j]);
            }
        }

        return max;
    }
}