大廠面試高頻題詳解：包裹黑色像素點的最小矩形

一個由二進制矩陣表示的圖，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

算法：二分

算法思路

代碼思路

複雜度分析

Leave a Reply Cancel reply