难度: Hard
Submission
运行时间: 36 ms
内存: 17.7 MB
class Solution:
def minArea(self, image: List[List[str]], x: int, y: int) -> int:
# using BS
m, n = len(image), len(image[0])
# search for rows
def searchRows(i, j, check):
upper, lower = i, j
while upper < lower:
mid = upper + (lower - upper) // 2
c = sum([image[mid][k] == '1' for k in range(n)])
if (c > 0) == check:
lower = mid
else:
upper = mid + 1
return upper
def searchCols(i, j, check):
left, right = i, j
while left < right:
mid = left + (right - left) // 2
c = sum([image[k][mid] == '1' for k in range(m)])
if (c > 0) == check:
right = mid
else:
left = mid + 1
return left
l, r = searchCols(0, y, True), searchCols(y+1, n, False)
u, b = searchRows(0, x, True), searchRows(x + 1, m, False)
# print(l, r, u, b)
return (b - u) * (r - l)
Explain
该题目要求找到包含所有'1'（黑色像素）的最小矩形区域。题解使用了二分查找方法来确定这个矩形的上下左右边界。具体地，先通过两个辅助函数 searchCols 和 searchRows 来确定四个边界。searchCols 函数用来确定左右边界，searchRows 函数用来确定上下边界。对于每个方向的边界查找，当在中间行或列找到至少一个'1'时，这个位置是有效的，反之无效，据此调整二分查找的范围。最终计算出的上下左右四个边界构成的矩形即为结果。
时间复杂度: O((m+n) log(m+n))
空间复杂度: O(1)
class Solution:
def minArea(self, image: List[List[str]], x: int, y: int) -> int:
# Initialize the dimensions of the image
m, n = len(image), len(image[0])
# Define function to search for horizontal boundaries
def searchRows(i, j, check):
upper, lower = i, j
while upper < lower:
mid = upper + (lower - upper) // 2
# Check if current row has at least one '1'
c = sum([image[mid][k] == '1' for k in range(n)])
if (c > 0) == check:
lower = mid
else:
upper = mid + 1
return upper
# Define function to search for vertical boundaries
def searchCols(i, j, check):
left, right = i, j
while left < right:
mid = left + (right - left) // 2
# Check if current column has at least one '1'
c = sum([image[k][mid] == '1' for k in range(m)])
if (c > 0) == check:
right = mid
else:
left = mid + 1
return left
# Compute the boundaries using the helper functions
l, r = searchCols(0, y, True), searchCols(y+1, n, False)
u, b = searchRows(0, x, True), searchRows(x + 1, m, False)
# Return the area of the rectangle defined by the boundaries
return (b - u) * (r - l)
Explore
在这个问题中，我们需要确定包含所有'1'的最小矩形边界。为了找到有效的边界，我们必须确认某一行或列是否有贡献（即至少包含一个'1'）。如果一行或列至少包含一个'1'，这意味着该行或列至少是部分边界。通过这种方式，我们可以使用二分查找方法有效地确定边界位置，从而缩小搜索范围，提高效率。
在这个算法中，目标是寻找到包含所有'1'的最小矩形边界。当我们在某个中点发现'1'时，这表示当前中点向边界方向的搜索是有效的，因此我们应该向这个方向继续缩小搜索范围，以便更精确地锁定边界。如果扩大范围，我们可能会包含更多不必要的区域，不符合最小化矩形的要求。
在searchCols函数中，我们从一个已知包含'1'的点(y)开始寻找边界。使用y作为左边界查找的结束（右边界）是基于这样一个假设：y列本身可能是需要的最左边界或更左。而使用y+1作为右边界查找的开始是基于假设：y列已经包含在内，我们需要从下一列开始确定不包含'1'的列，从而确定最右边界。这样的分界确保了查找范围的正确性和算法的高效性。
如果输入的图像中全部为'0'，当前算法可能不会正确运行，因为它依赖于找到至少一列或一行包含'1'来确定边界。在这种情况下，二分查找的check部分永远不会为true，可能导致无限循环或错误的边界返回。为了处理这种情况，我们可以在算法开始前添加一个预检查步骤，即遍历整个图像查看是否至少存在一个'1'。如果不存在'1'，则直接返回面积为0或相应的错误/空矩形提示。