题目描述
图片在计算机处理中往往是使用二维矩阵来表示的。
给你一个大小为 m x n 的二进制矩阵 image 表示一张黑白图片，0 代表白色像素，1 代表黑色像素。
黑色像素相互连接，也就是说，图片中只会有一片连在一块儿的黑色像素。像素点是水平或竖直方向连接的。
给你两个整数 x 和 y 表示某一个黑色像素的位置，请你找出包含全部黑色像素的最小矩形（与坐标轴对齐），并返回该矩形的面积。
你必须设计并实现一个时间复杂度低于 O(mn) 的算法来解决此问题。
示例 1：
输入：image = [["0","0","1","0"],["0","1","1","0"],["0","1","0","0"]], x = 0, y = 2
输出：6
示例 2：
输入：image = [["1"]], x = 0, y = 0
输出：1
提示：
m == image.lengthn == image[i].length1 <= m, n <= 100image[i][j] 为 '0' 或 '1'1 <= x < m1 <= y < nimage[x][y] == '1'image 中的黑色像素仅形成一个 组件
解法
方法一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48 | 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)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66 | 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);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54 | 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);
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60 | 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)
}
|