包含全部黑色像素的最小矩形
难度:
标签:
题目描述
代码结果
运行时间: 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'来判断中点是否有效?
▷🦆
在searchCols和searchRows函数中,为什么在找到'1'时对应的行动是缩小范围而不是扩大?
▷🦆
searchCols函数中,当从左边界开始时为什么使用y作为起始的右边界,而从右边界开始时使用y+1作为起始的左边界?
▷🦆
如果输入的图像中没有任何'1'(全部为'0'),此算法是否还会正确运行?如果不会,应该如何修改算法来处理这种情况?
▷