图片在计算机处理中往往是使用二维矩阵来表示的。
假设，这里我们用的是一张黑白的图片，那么 0 代表白色像素，1 代表黑色像素。
其中黑色的像素他们相互连接，也就是说，图片中只会有一片连在一块儿的黑色像素（像素点是水平或竖直方向连接的）。
那么，给出某一个黑色像素点 (x, y) 的位置，你是否可以找出包含全部黑色像素的最小矩形（与坐标轴对齐）的面积呢？
示例:
输入: [ "0010", "0110", "0100" ]和 x = 0,y = 2输出: 6
二分查找，时间复杂度 O(mlogn + nlogm)。
class Solution:
def minArea(self, image: List[List[str]], x: int, y: int) -> int:
m, n = len(image), len(image[0])
left, right = 0, x
while left < right:
mid = (left + right) >> 1
c = 0
while c < n and image[mid][c] == '0':
c += 1
if c < n:
right = mid
else:
left = mid + 1
u = left
left, right = x, m - 1
while left < right:
mid = (left + right + 1) >> 1
c = 0
while c < n and image[mid][c] == '0':
c += 1
if c < n:
left = mid
else:
right = mid - 1
d = left
left, right = 0, y
while left < right:
mid = (left + right) >> 1
r = 0
while r < m and image[r][mid] == '0':
r += 1
if r < m:
right = mid
else:
left = mid + 1
l = left
left, right = y, n - 1
while left < right:
mid = (left + right + 1) >> 1
r = 0
while r < m and image[r][mid] == '0':
r += 1
if r < m:
left = mid
else:
right = mid - 1
r = left
return (d - u + 1) * (r - l + 1)class Solution {
public int minArea(char[][] image, int x, int y) {
int m = image.length, n = image[0].length;
int left = 0, right = x;
while (left < right) {
int mid = (left + right) >> 1;
int c = 0;
while (c < n && image[mid][c] == '0') {
++c;
}
if (c < n) {
right = mid;
} else {
left = mid + 1;
}
}
int u = left;
left = x;
right = m - 1;
while (left < right) {
int mid = (left + right + 1) >> 1;
int c = 0;
while (c < n && image[mid][c] == '0') {
++c;
}
if (c < n) {
left = mid;
} else {
right = mid - 1;
}
}
int d = left;
left = 0;
right = y;
while (left < right) {
int mid = (left + right) >> 1;
int r = 0;
while (r < m && image[r][mid] == '0') {
++r;
}
if (r < m) {
right = mid;
} else {
left = mid + 1;
}
}
int l = left;
left = y;
right = n - 1;
while (left < right) {
int mid = (left + right + 1) >> 1;
int r = 0;
while (r < m && image[r][mid] == '0') {
++r;
}
if (r < m) {
left = mid;
} else {
right = mid - 1;
}
}
int r = left;
return (d - u + 1) * (r - l + 1);
}
}class Solution {
public:
int minArea(vector<vector<char>>& image, int x, int y) {
int m = image.size(), n = image[0].size();
int left = 0, right = x;
while (left < right)
{
int mid = (left + right) >> 1;
int c = 0;
while (c < n && image[mid][c] == '0') ++c;
if (c < n) right = mid;
else left = mid + 1;
}
int u = left;
left = x;
right = m - 1;
while (left < right)
{
int mid = (left + right + 1) >> 1;
int c = 0;
while (c < n && image[mid][c] == '0') ++c;
if (c < n) left = mid;
else right = mid - 1;
}
int d = left;
left = 0;
right = y;
while (left < right)
{
int mid = (left + right) >> 1;
int r = 0;
while (r < m && image[r][mid] == '0') ++r;
if (r < m) right = mid;
else left = mid + 1;
}
int l = left;
left = y;
right = n - 1;
while (left < right)
{
int mid = (left + right + 1) >> 1;
int r = 0;
while (r < m && image[r][mid] == '0') ++r;
if (r < m) left = mid;
else right = mid - 1;
}
int r = left;
return (d - u + 1) * (r - l + 1);
}
};func minArea(image [][]byte, x int, y int) int {
m, n := len(image), len(image[0])
left, right := 0, x
for left < right {
mid := (left + right) >> 1
c := 0
for c < n && image[mid][c] == '0' {
c++
}
if c < n {
right = mid
} else {
left = mid + 1
}
}
u := left
left, right = x, m-1
for left < right {
mid := (left + right + 1) >> 1
c := 0
for c < n && image[mid][c] == '0' {
c++
}
if c < n {
left = mid
} else {
right = mid - 1
}
}
d := left
left, right = 0, y
for left < right {
mid := (left + right) >> 1
r := 0
for r < m && image[r][mid] == '0' {
r++
}
if r < m {
right = mid
} else {
left = mid + 1
}
}
l := left
left, right = y, n-1
for left < right {
mid := (left + right + 1) >> 1
r := 0
for r < m && image[r][mid] == '0' {
r++
}
if r < m {
left = mid
} else {
right = mid - 1
}
}
r := left
return (d - u + 1) * (r - l + 1)
}