[LeetCode]Smallest Rectangle Enclosing Black Pixels

如果black pixel不多的话我们只需要全部BFS/DFS找到左右边界即可。但是如果black pixel很多的话我们还有更好的方法，显然我们只需要对上下界和左右边界进行binary search即可，判断当前行/列有没有black pixel然后相应地进行移动即可。思路不难，但是实现的话，我们要考虑如何不让代码重复，因为搜索行列和lowerbound和upperbound的代码是很相似却又些微不同的。
首先对于lowerbound和upperbound，可以参考Search for Range，如果我们搜索下边界和上边界的后一个数的话，是可以共用代码的。那么对于行和列的共用代码，其实并不难，参考下面的代码很容易懂。时间复杂度O(m * log n + n * log m)，常数空间，代码如下：

	class Solution {
	public:
	int minArea(vector<vector<char>>& image, int x, int y) {
	int m = image.size(), n = m? image[0].size(): 0;
	int top = search(image, 0, x, n, true, true);
	int bottom = search(image, x + 1, m, n, true, false);
	int left = search(image, 0, y, m, false, true);
	int right = search(image, y + 1, n, m, false, false);
	return (bottom - top) * (right - left);
	}
	private:
	//for lowerbound, reurn lowerbound; for upper bound, return upperbould + 1
	int search(vector<vector<char>>& image, int lo, int hi, int end, bool isRow, bool isLowerBound)
	{
	while(lo < hi)
	{
	int mid = lo + (hi - lo) / 2;
	bool hasBlack = false;
	for(int j = 0; j < end; ++j)
	{
	if(isBlack(image, mid, j, isRow))
	{
	hasBlack = true;
	break;
	}
	}
	if(isLowerBound)
	{
	if(hasBlack)
	hi = mid;
	else
	lo = mid + 1;
	}
	else
	{
	if(hasBlack)
	lo = mid + 1;
	else
	hi = mid;
	}
	}
	return lo;
	}
	bool isBlack(vector<vector<char>>& image, int i, int j, bool isRow)
	{
	return isRow? image[i][j] == '1': image[j][i] == '1';
	}
	};

view raw Smallest Rectangle Enclosing Black Pixels.cpp hosted with ❤ by GitHub