题目地址

https://leetcode-cn.com/problems/max-black-square-lcci/

题目描述

给定一个方阵，其中每个单元(像素)非黑即白。设计一个算法，找出 4 条边皆为黑色像素的最大子方阵。

返回一个数组 [r, c, size] ，其中 r, c 分别代表子方阵左上角的行号和列号，size 是子方阵的边长。若有多个满足条件的子方阵，返回 r 最小的，若 r 相同，返回 c 最小的子方阵。若无满足条件的子方阵，返回空数组。

示例 1:

输入:
[
   [1,0,1],
   [0,0,1],
   [0,0,1]
]
输出: [1,0,2]
解释: 输入中 0 代表黑色，1 代表白色，标粗的元素即为满足条件的最大子方阵
示例 2:

输入:
[
   [0,1,1],
   [1,0,1],
   [1,1,0]
]
输出: [0,0,1]
提示：

matrix.length == matrix[0].length <= 200

题解

暴力枚举

class Solution {
    public int[] findSquare(int[][] matrix) {
        int length = matrix.length;
        int resultR = 0, resultC = 0, resultSize = 0;

        for (int r = 0; r < length; ++ r) {
            for (int c = 0; c < length; ++ c) {
                int maxSize = Math.min(length - r, length - c);
                for (int size = maxSize; size >= 1; -- size) {
                    if (isMatrix(matrix, r, c, size)) {
                        if (size > resultSize) {
                            resultR = r;
                            resultC = c;
                            resultSize = size;
                        }
                        break;
                    }
                }
            }
        }

        // 没有一个黑方阵的情况下要返回空数组
        if (resultSize == 0) {
            return new int[]{};
        }

        return new int[]{resultR, resultC, resultSize};
    }

    public boolean isMatrix(int[][] matrix, int r, int c, int size) {
        int rr = r + size - 1;
        int cc = c + size - 1;

        // 上下左右四条边
        
        // 遍历上面和上面的两条边
        for (int i = c; i <= cc; ++ i) {
            // 上面的边
            if (matrix[r][i] == 1) {
                return false;
            }
            // 下面的边
            if (matrix[rr][i] == 1) {
                return false;
            }
        }

        // 遍历左边和右边的两条边
        for (int i = r; i <= rr; ++ i) {
            // 左边的边
            if (matrix[i][c] == 1) {
                return false;
            }
            // 右边的边
            if (matrix[i][cc] == 1) {
                return false;
            }
        }

        return true;
    }
}

时间复杂度为：O(n^4)，n 为原矩阵的边长。

上面遍历矩阵顶点和 size 的操作是必需的。

可以看看怎么优化 isMatrix() 的逻辑，通过预处理可以在常量时间判断 (r, c, size) 是否是一个矩阵。

预处理

class Solution {
    public int[] findSquare(int[][] matrix) {
        int length = matrix.length;
        int resultR = 0, resultC = 0, resultSize = 0;

        int[][] minBottomAndRight = buildMinBottomAndRight(matrix);
        int[][] minUpAndLeft = buildMinTopAndLeft(matrix);

        for (int r = 0; r < length; ++ r) {
            for (int c = 0; c < length; ++ c) {
                int maxSize = minBottomAndRight[r][c];
                for (int size = maxSize; size >= 1; -- size) {
                    int rr = r + size - 1;
                    int cc = c + size - 1;
                    boolean isMatrix = minUpAndLeft[rr][cc] >= size;
                    if (isMatrix) {
                        if (size > resultSize) {
                            resultR = r;
                            resultC = c;
                            resultSize = size;
                        }
                        break;
                    }
                }
            }
        }

        if (resultSize == 0) {
            return new int[]{};
        }

        return new int[]{resultR, resultC, resultSize};
    }

    public int[][] buildMinBottomAndRight(int[][] matrix) {
        int length = matrix.length;
        int[][] bottomAndRight = new int[length][length];
        for (int r = 0; r < length; ++ r) {
            for (int c = 0; c < length; ++ c) {
                // 计算下面的边有多少连续的黑色
                int bottom = 0;
                for (int rr = r; rr < length; ++ rr) {
                    if (matrix[rr][c] == 1) {
                        break;
                    }
                    bottom ++;
                }

                // 计算右边有多少连续的黑色
                int right = 0;
                for (int cc = c; cc < length; ++ cc) {
                    if (matrix[r][cc] == 1) {
                        break;
                    }
                    right ++;
                }

                bottomAndRight[r][c] = Math.min(bottom, right);
            }
        }
        return bottomAndRight;
    }

    public int[][] buildMinTopAndLeft(int[][] matrix) {
        int length = matrix.length;
        int[][] upAndLeft = new int[length][length];
        for (int r = 0; r < length; ++ r) {
            for (int c = 0; c < length; ++ c) {
                // 计算上面的边有多少连续的黑色
                int up = 0;
                for (int rr = r; rr >= 0; -- rr) {
                    if (matrix[rr][c] == 1) {
                        break;
                    }
                    up ++;
                }

                // 计算左边有多少连续的黑色
                int left = 0;
                for (int cc = c; cc >= 0; -- cc) {
                    if (matrix[r][cc] == 1) {
                        break;
                    }
                    left ++;
                }

                upAndLeft[r][c] = Math.min(up, left);
            }
        }
        return upAndLeft;
    }
}

时间复杂度为：O(n^3)，n 为原矩阵的边长。
空间复杂度为：O(n^2)，n 为原矩阵的边长。

参考

• https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/max-black-square-lcci