大厂面试高频题详解：包裹黑色像素点的最小矩形

2023-11-16 20:58:39

一个由二进制矩阵表示的图，0 表示白色像素点，1 表示黑色像素点。黑色像素点是联通的，即只有一块黑色区域。像素是水平和竖直连接的，给一个黑色像素点的坐标 (x, y) ，返回囊括所有黑色像素点的矩阵的最小面积。

样例 1:

输入：["0010","0110","0100"]，x=0，y=2
输出：6
解释：
矩阵左上角坐标是(0, 1), 右下角的坐标是(2, 2)

样例 2:

输入：["1110","1100","0000","0000"], x = 0, y = 1
输出：6
解释：
矩阵左上角坐标是(0,  0), 右下角坐标是(1, 3)

算法：二分

关于BFS和DFS
BFS和DFS的做法就是遍历这个黑色像素连通块，得到各个方向上的坐标极值，时间复杂度O(K)，K为黑色像素点个数，这种做法在黑色像素点数量巨大时效率极低。

另外关于BFS和DFS如何选择，这里建议使用BFS，因为DFS会占用大量的系统栈，空间复杂度上要劣于BFS
下面我们来介绍一种在大部分情况下空间和时间上均优于DFS和BFS的算法——二分

算法思路

二分找到四个方向上黑色像素点出现的坐标极值

代码思路

这边以二分最左侧黑色像素为例

设置左指针为0，右指针为y，因为我们保证y列上存在黑色像素，最左侧黑色像素所在列一定在y或者其左侧
若mid所在列存在黑色像素，说明最左侧黑色像素在mid列或者其左侧，r = mid，否则l = mid
判断l列是否存在黑色像素，若存在则left = l，否则left = r。注意一定要先判l列，因为r可能存在黑色像素，但并不是最左侧

以此类推继续找到最右侧，最上侧，最下侧的黑色像素所在列或行
计算面积(right - left + 1) * (bottom - top + 1)并将其返回
这里提一种优化，找到最左处和最右处的黑色像素位置left和right后，在找最上和最下坐标时，对于行的判断只需要扫描[row,left]到[row,right]即可

复杂度分析

空间复杂度：O(1)
时间复杂度：O(MlogN+NlogM)（最坏情况）
最坏情况即只有一个黑色像素点，那么每次判断列上或行上是否又黑色像素点需要扫描完整列或整行

二分的做法当遇到黑色像素点很少且给出的矩阵很大时效率会变得极低，而此时BFS的效率会相对高很多
后记
能否做到在任何情况下效率都显得相对较高呢？我们可以设定一个阈值cnt，先进行BFS遍历，当遍历次数达到cnt时改用二分法进行计算

public class Solution {

    /**
     * @param image: a binary matrix with '0' and '1'
     * @param x: the location of one of the black pixels
     * @param y: the location of one of the black pixels
     * @return: an integer
     */

    public int minArea(char[][] image, int x, int y) {
        if (image == null || image.length == 0 || image[0].length == 0) {
            return 0;
        }

        int n = image.length;
        int m = image[0].length;
        int l = 0, r = 0;
        int left = 0, right = 0, top = 0, bottom = 0;
        //二分最左侧黑色像素坐标
        l = 0;
        r = y;
        while (l + 1 < r) {
            int mid = l + (r - l) / 2;
            if (check_column(image, mid)) {
                r = mid;
            } else {
                l = mid;
            }
        }
        if (check_column(image, l)){
            left = l;
        }else{
            left = r;
        }
        //二分最右侧黑色像素坐标
        l = y;
        r = m - 1
        while (l + 1 < r) {
            int mid = l + (r - l) / 2;
            if (check_column(image, mid)) {
                l = mid;
            } else {
                r = mid;
            }
        }
        if (check_column(image, r)) {
            right = r;
        }else{
            right = l;
        }
        //二分最上侧黑色像素坐标
        l = 0;
        r = x;
        while (l + 1 < r) {
            int mid = l + (r - l) / 2;
            if (check_row(image, mid, left, right)) {
                r = mid;
            } else {
                l = mid;
            }
        }       

        if (check_row(image, l, left, right)) {
            top = l;
        }else{
            top = r;
        }
        //二分最下侧黑色像素坐标
        l = x;
        r = n - 1;
        while (l + 1 < r) {
            int mid = l + (r - l) / 2;
            if (check_row(image, mid, left, right)) {
                l = mid;
            } else {
                r = mid;
            }
        }      

        if (check_row(image, r, left, right)) {
            bottom = r;
        }else{
            bottom = l;
        }
        return (right - left + 1) * (bottom - top + 1);
    }

    //判断列上是否存在黑色像素
    private boolean check_column(char[][] image, int col) {
        for (int i = 0; i < image.length; i++) {
            if (image[i][col] == '1') {
                return true;
            }
        }
        return false;
    }
    //判断行上是否存在黑色像素
    private boolean check_row(char[][] image, int row ,int left ,int right) {
        for (int j = left; j <= right; j++) {
            if (image[row][j] == '1') {
                return true;
            }
        }
        return false;
    }
}

更多题解参考:九章官网solution

码农公寓

算法：二分

算法思路

代码思路

复杂度分析

相关文章