面试题 17.23. 最大黑方阵 

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
class Solution {
    public int[] findSquare(int[][] matrix) {
        int[] res = new int[3];
        int n = matrix.length;

        // 注意特判，避免后续索引越界
        if (n == 1) {
            if (matrix[0][0] == 0) {
                return new int[]{0, 0, 1};
            } else {
                return new int[0];
            }
        }

        // 定义 dp[i][j][k] 为以 matrix[i][j] 为左上角，向 k 方向的最大黑色像素长度，k = 0 为向右，k = 1 为向下
        int[][][] dp = new int[n][n][2];

        // 因为依赖下一 行/列，所以倒序计算 dp
        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (matrix[i][j] == 1) {
                    continue;
                }

                if (i == n - 1) {
                    // 最后一行，仅判断当前点
                    dp[i][j][1] = 1;
                } else {
                    // 聚合下一行的结果
                    dp[i][j][1] = dp[i + 1][j][1] + 1;
                }

                if (j == n - 1) {
                    // 最后一列，仅判断当前点
                    dp[i][j][0] = 1;
                } else {
                    // 聚合下一列的结果
                    dp[i][j][0] = dp[i][j + 1][0] + 1;
                }

                int length = Math.min(dp[i][j][0], dp[i][j][1]);
                while (length >= res[2]) {
                    // 判断剩余两条边是否满足条件
                    if (dp[i + length - 1][j][0] >= length && dp[i][j + length - 1][1] >= length) {
                        res[0] = i;
                        res[1] = j;
                        res[2] = length;
                        break;
                    }
                    length--;
                }
            }
        }

        return res;
    }
}

References

面试题 17.23. 最大黑方阵