预处理练习之最大正方形

题目描述

给你一个N*M的矩阵，里面全是0或者1，请返回矩阵中边框全是1的最大正方形。

思路分析

求一个大矩阵中的小正方形，首先，需要确定矩阵中的任意一个点，需要遍历二维矩阵，然后，从这个点为左上角的正方形，有多少个？正方形的边长，向右方和下方扩展，直到其中一边抵达矩阵边界为止。
因此，找出矩阵中的小正方形，需要遍历二维数组，这是O(N平方)的复杂度，遍历正方形边长到矩阵边界，又是O(N)，总的时间复杂度就是O(n三次方)，然后，题目要求求出边界全是1的，再循环遍历四条边界，还需要写四个不嵌套的循环，因此，总的时间复杂度是O(n的四次方)
复杂代码就不写了，直接上预处理后的代码，对于此题，二维数组遍历无法优化，遍历边长也无法优化，唯一能优化的位置就是判断边界是否是全1这一步，我们可以提前用二维数组把1的信息统计出来，然后直接拿出来判断。

代码

    public static int f3(int[][] arr){
        //记录每一位右边有多少连续的1
        int[][] right=new int[arr.length][arr[0].length];
        //记录每一位下边有多少连续的1
        int[][] down=new int[arr.length][arr[0].length];
        //预处理右边有多少连续的1
        for (int i = arr.length-1; i >= 0 ; i--) {
            int before=0;
            for (int j = arr[0].length-1; j >= 0 ; j--) {
                if(arr[i][j]==1){
                    right[i][j]=1+before;
                    before=right[i][j];
                }else {
                    right[i][j]=0;
                    before=0;
                }
            }
        }
        //预处理下边有多少连续的1
        for (int j = arr[0].length-1; j >= 0 ; j--) {
            int before=0;
            for (int i = arr.length-1; i >= 0 ; i--) {
                if(arr[i][j]==1){
                    down[i][j]=1+before;
                    before=down[i][j];
                }else {
                    down[i][j]=0;
                    before=0;
                }
            }
        }

        int max=0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                for (int k = 1; k <= Math.min(arr.length-i,arr[0].length-j); k++) {
                    if(right[i][j]>=k && down[i][j]>=k && right[i+k-1][j]>=k && down[i][j+k-1]>=k){
                        if(max<k){
                            max=k;
                        }
                    }
                }
            }
        }
        return max;
    }