lintcode 631 · 最大矩阵II【矩阵 中等 vip】

题目

https://www.lintcode.com/problem/631

给出一个只有 0 和 1 组成的二维矩阵。
找出最大的一个子矩阵，使得这个子矩阵的主对角线元素均为 1 ，其他元素均为 0 。


你可以认为所求的矩阵一定是一个方阵。
主对角线指的是从左上角到右下角的一条对角线。

样例
例1:

输入:
[[1,0,1,0,0],[1,0,0,1,0],[1,1,0,0,1],[1,0,0,1,0]]
输出:
9
解释:
[0,2]->[2,4]
例2:

输入:
[[1,0,1,0,1],[1,0,0,1,1],[1,1,1,1,1],[1,0,0,1,0]]
输出:
4
解释:
[0,2]->[1,3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

答案

public class Solution {
    /**
     * @param matrix: a matrix of 0 an 1
     * @return: an integer
     */
    public int maxSquare2(int[][] matrix) {
            int n = matrix.length,m=matrix[0].length,max =0;
        int[][] dp = new int[n][m];

        for (int i = 0; i <n ; i++) {
            if(matrix[i][0] ==1){
                dp[i][0] =1;
                max =1;
            }
        }

        for (int j = 0; j < m; j++) {
            if(matrix[0][j] ==1){
                dp[0][j] =1;
                max =1;
            }
        }

        for (int i = 1; i <n ; i++) {
            for (int j = 1; j <m ; j++) {
                if(matrix[i][j] !=1){
                    continue;
                }
                dp[i][j]=1;

                if(all0(matrix,i,j,dp[i-1][j-1])){
                    dp[i][j] +=dp[i-1][j-1];
                }
                max =Math.max(max,dp[i][j]);
            }
        }

        return max*max;
    }

    public static boolean all0(int[][] mattrix,int i,int j,int offset){
        while (offset>0){
            if(mattrix[i-offset][j] ==1 || mattrix[i][j-offset] ==1)
                return false;

            offset--;
        }

        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

本地测试代码

public class LC631 {

    public static int maxSquare2(int[][] matrix) {
        int n = matrix.length,m=matrix[0].length,max =0;
        int[][] dp = new int[n][m];

        for (int i = 0; i <n ; i++) {
            if(matrix[i][0] ==1){
                dp[i][0] =1;
                max =1;
            }
        }

        for (int j = 0; j < m; j++) {
            if(matrix[0][j] ==1){
                dp[0][j] =1;
                max =1;
            }
        }

        for (int i = 1; i <n ; i++) {
            for (int j = 1; j <m ; j++) {
                if(matrix[i][j] !=1){
                    continue;
                }
                dp[i][j]=1;

                if(all0(matrix,i,j,dp[i-1][j-1])){
                    dp[i][j] +=dp[i-1][j-1];
                }
                max =Math.max(max,dp[i][j]);
            }
        }

        return max*max;
    }

    public static boolean all0(int[][] mattrix,int i,int j,int offset){
        while (offset>0){
            if(mattrix[i-offset][j] ==1 || mattrix[i][j-offset] ==1)
                return false;

            offset--;
        }

        return true;
    }
    public static void main(String[] args) {
        System.out.println(maxSquare2(new int[][]
                {
                        {1,0,1,0,0},
                        {1,0,0,1,0},
                        {1,1,0,0,1},
                        {1,0,0,1,0}})); //9

        System.out.println(maxSquare2(new int[][]
                {
                        {1,0,1,0,1},
                        {1,0,0,1,1},
                        {1,1,1,1,1},
                        {1,0,0,1,0}})); //4
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64