302. Smallest Rectangle Enclosing Black Pixels

题目链接：

首先想到的是dfs查找，用left，right，up，down四个变量分别表示最左边，最右边最上面和最下面，最后面积就是(right-left+1) * (down-up+1)

public class Solution {    public int minArea(char[][] image, int x, int y) {        left = y; right = y;        up = x; down = x;        dfs(image, new boolean[image.length][image[0].length], x, y);                return (right - left + 1) * (down - up + 1);    }    int left, right, up, down;    int[][] dirs = new int[][] {
   {-1, 0}, {1, 0}, {0, -1}, {0, 1}};        private void dfs(char[][] image, boolean[][] visited, int x, int y) {        int m = image.length, n = image[0].length;        if(x < 0 || x >= m || y < 0 || y >= n || visited[x][y] || image[x][y] == '0') return;        visited[x][y] = true;        // update 4 boundary        left = Math.min(left, x);  right = Math.max(right, x);        up = Math.min(up, y); down = Math.max(down, y);                for(int[] dir : dirs) {            dfs(image, visited, x + dir[0], y + dir[1]);        }    }}

标签写的是binary search，那么考虑枚举的方式，四个边界的范围分别是：left: [0, y+1], right: [y, n], up: [0, x+1], down: [x, m]

public class Solution {    public int minArea(char[][] image, int x, int y) {        int left, right, up, down;        int m = image.length, n = image[0].length;        left = binarySearch(image, 0, y, 0, m, true, true);        right = binarySearch(image, y+1, n, 0, m, true, false);        up = binarySearch(image, 0, x, left, right, false, true);        down = binarySearch(image, x+1, m, left, right, false, false);        return (right - left) * (down - up);    }        private int binarySearch(char[][] image, int start, int end, int l, int r, boolean col, boolean inc) {        while(start < end) {            int k = l, mid = start + (end - start) / 2;            while(k < r && (col ? image[k][mid] : image[mid][k]) == '0') k++;            // k < r: find black pixel:             // start = mid + 1 if right or down, end = mid if left or up            if((k < r) == inc) end = mid;            else start = mid + 1;        }                return start;    }}