九章算法 | Google 面试题：包裹黑色像素点的最小矩形

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

在线评测地址：LintCode 领扣

样例 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的算法——二分

算法思路

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

代码思路

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

1. 设置左指针为0，右指针为​y​，因为我们保证​y​列上存在黑色像素，最左侧黑色像素所在列一定在​y​或者其左侧
2. 若​mid​所在列存在黑色像素，说明最左侧黑色像素在​mid​列或者其左侧，​r = mid​，否则​l = mid​
3. 判断​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;
    }
} 

更多题解参考：九章算法