leetcode
leetcode 251 ~ 300
包含全部黑色像素的最小矩形

包含全部黑色像素的最小矩形

难度:

标签:

题目描述

代码结果

运行时间: 36 ms, 内存: 17.7 MB


/* 
 * 题目:包含全部黑色像素的最小矩形 
 * 解题思路: 
 * 1. 使用Java Stream API进行矩阵的遍历和索引计算。 
 */ 
import java.util.stream.IntStream; 
public class Solution { 
    public int minArea(char[][] image, int x, int y) { 
        int minX = IntStream.range(0, image.length) 
                             .filter(i -> IntStream.range(0, image[0].length).anyMatch(j -> image[i][j] == '1')) 
                             .min().orElse(x); 
        int maxX = IntStream.range(0, image.length) 
                             .filter(i -> IntStream.range(0, image[0].length).anyMatch(j -> image[i][j] == '1')) 
                             .max().orElse(x); 
        int minY = IntStream.range(0, image[0].length) 
                             .filter(j -> IntStream.range(0, image.length).anyMatch(i -> image[i][j] == '1')) 
                             .min().orElse(y); 
        int maxY = IntStream.range(0, image[0].length) 
                             .filter(j -> IntStream.range(0, image.length).anyMatch(i -> image[i][j] == '1')) 
                             .max().orElse(y); 
        return (maxX - minX + 1) * (maxY - minY + 1); 
    } 
}

解释

方法:

该题目要求找到包含所有'1'(黑色像素)的最小矩形区域。题解使用了二分查找方法来确定这个矩形的上下左右边界。具体地,先通过两个辅助函数 searchCols 和 searchRows 来确定四个边界。searchCols 函数用来确定左右边界,searchRows 函数用来确定上下边界。对于每个方向的边界查找,当在中间行或列找到至少一个'1'时,这个位置是有效的,反之无效,据此调整二分查找的范围。最终计算出的上下左右四个边界构成的矩形即为结果。

时间复杂度:

O((m+n) log(m+n))

空间复杂度:

O(1)

代码细节讲解

🦆
在二分查找中,为什么需要通过检查某一行或列中是否至少有一个'1'来判断中点是否有效?
在这个问题中,我们需要确定包含所有'1'的最小矩形边界。为了找到有效的边界,我们必须确认某一行或列是否有贡献(即至少包含一个'1')。如果一行或列至少包含一个'1',这意味着该行或列至少是部分边界。通过这种方式,我们可以使用二分查找方法有效地确定边界位置,从而缩小搜索范围,提高效率。
🦆
在searchCols和searchRows函数中,为什么在找到'1'时对应的行动是缩小范围而不是扩大?
在这个算法中,目标是寻找到包含所有'1'的最小矩形边界。当我们在某个中点发现'1'时,这表示当前中点向边界方向的搜索是有效的,因此我们应该向这个方向继续缩小搜索范围,以便更精确地锁定边界。如果扩大范围,我们可能会包含更多不必要的区域,不符合最小化矩形的要求。
🦆
searchCols函数中,当从左边界开始时为什么使用y作为起始的右边界,而从右边界开始时使用y+1作为起始的左边界?
在searchCols函数中,我们从一个已知包含'1'的点(y)开始寻找边界。使用y作为左边界查找的结束(右边界)是基于这样一个假设:y列本身可能是需要的最左边界或更左。而使用y+1作为右边界查找的开始是基于假设:y列已经包含在内,我们需要从下一列开始确定不包含'1'的列,从而确定最右边界。这样的分界确保了查找范围的正确性和算法的高效性。
🦆
如果输入的图像中没有任何'1'(全部为'0'),此算法是否还会正确运行?如果不会,应该如何修改算法来处理这种情况?
如果输入的图像中全部为'0',当前算法可能不会正确运行,因为它依赖于找到至少一列或一行包含'1'来确定边界。在这种情况下,二分查找的check部分永远不会为true,可能导致无限循环或错误的边界返回。为了处理这种情况,我们可以在算法开始前添加一个预检查步骤,即遍历整个图像查看是否至少存在一个'1'。如果不存在'1',则直接返回面积为0或相应的错误/空矩形提示。

相关问题