LC302. Smallest Rectangle Enclosing Black Pixels
An image is represented by a binary matrix with 0 as a white pixel and 1 as a black pixel. The black pixels are connected, i.e., there is only one black region. Pixels are connected horizontally and vertically. Given the location (x, y) of one of the black pixels, return the area of the smallest (axis-aligned) rectangle that encloses all black pixels.
For example, given the following image:
[
"0010",
"0110",
"0100"
]
return 6.
Naive DFS:
找到覆盖所有1的最小矩形, 我很naive的用dfs做了, 10ms, O(n^2), O(n^2).
public class Solution {
public int minArea(char[][] image, int x, int y) {
// dfs
if(image == null || image.length == 0) return 0;
int m = image.length, n = image[0].length;
int[] res = new int[4]; // minx, miny, maxx, maxy
res[0] = Integer.MAX_VALUE;
res[1] = Integer.MAX_VALUE;
res[2] = Integer.MIN_VALUE;
res[3] = Integer.MIN_VALUE;
dfs(image, x, y, res, m, n);
// for(int r:res)
//System.out.print(r);
return (res[2]-res[0]+1)*(res[3]-res[1]+1);
} // minArea
private void dfs(char[][] image, int x, int y, int[] res, int m, int n){
int[] dx = {1, -1, 0, 0};
int[] dy = {0, 0, -1, 1};
if(x < 0 || x >= m || y >= n || y < 0 || image[x][y] != '1') return;
if(image[x][y] == '1'){
res[0] = Math.min(res[0], x);
res[1] = Math.min(res[1], y);
res[2] = Math.max(res[2], x);
res[3] = Math.max(res[3], y);
image[x][y] = '2';
for(int i = 0; i < 4; i++) dfs(image, x + dx[i], y + dy[i], res, m, n);
}
return;
} // dfs
}
BinarySearch Solution:
写出又高效又优美的解答真是我一生的追求啊🙄
如果知道一个点的位置，二分查找寻找边界。(x, y)是给定的1位置，二分查找[0, y], 找最左边的1，[y+1, n)找最右边的0。上下同理👇。找左右边界花销O(mlgn), 上下边界O(nlgm), 总时间花销O(mlgn + nlgm). 1ms.
left = search col[0...y], find first col contain 1, right = search col[y+1, col], find first col contain all 0 top = search row [0...x], find first row contain 1, bottom = search row[x+1, row], find first row contian all 0
public class Solution {
public int minArea(char[][] image, int x, int y) {
if(image == null || image.length == 0) return 0;
int m = image.length, n = image[0].length;
// 2D binary search
int left = searchCol(0, y, 0, m, true, image);
int right = searchCol(y+1, n, 0, m, false, image);
int top = searchRow(0, x, left, right, true, image);
int bottom = searchRow(x, m, left, right, false, image);
return (right - left)*(bottom - top);
} // minArea
private int searchCol(int i, int j, int top, int bottom, boolean opt, char[][] image){
while(i != j){
int k = top, mid = i + (j - i)/2;
while(k < bottom && image[k][mid] == '0') k++;
// if we want to find the first col contains 1, when k != bottom we should search left
// if we want to find the first col is all 0, when k != bottom we sohuld search right
if(k < bottom == opt){
j = mid;
}else{
i = mid + 1;
}
}
return i;
} // searchCol
private int searchRow(int i, int j, int left, int right, boolean opt, char[][] image){
while( i != j){
int k = left, mid = i + (j - i)/2;
while(k < right && image[mid][k] == '0') k++;
// if we want to find the first row contains 1, when k != right we should search up
// if we want to find the first row is all 0, when k != bottom we sohuld search down
if(k < right == opt){
j = mid;
}else{
i = mid + 1;
}
}
return i;
} // searchRow
}