Article / 文章
LeetCode 第302题：包含全部黑色像素的最小矩形
给你一个图像数组 image 表示一个二维图像，图像中的每个像素要么是 0（表示白色），要么是 1（表示黑色）。 给你两个整数 x 和 y 表示一个黑色像素的位置。请你找出包含全部黑色像素的最小矩形的面积。 图像是一个二维矩阵，其中 0 表示白色像素，1 表示黑色像素。给定的黑色像素位置 (x, y) 一定是黑色像素。
📖 文章摘要
本文详细解析LeetCode第302题“包含全部黑色像素的最小矩形”，这是一道考察二分查找和矩阵处理的困难难度题目。文章提供了暴力搜索和二分查找两种实现方案，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合学习二分查找和矩阵处理的读者。
核心知识点： 二分查找、矩阵处理、边界处理
难度等级： 困难
推荐人群： 具备基础算法知识，想要提升二分查找和矩阵处理能力的开发者
题目描述
给你一个图像数组 image 表示一个二维图像，图像中的每个像素要么是 0（表示白色），要么是 1（表示黑色）。
给你两个整数 x 和 y 表示一个黑色像素的位置。请你找出包含全部黑色像素的最小矩形的面积。
图像是一个二维矩阵，其中 0 表示白色像素，1 表示黑色像素。给定的黑色像素位置 (x, y) 一定是黑色像素。
示例
示例 1：
输入：image = [["0","0","1","0"],["0","1","1","0"],["0","1","0","0"]], x = 0, y = 2
输出：6
解释：
上面的图像表示一个二维矩阵，其中：
- "0" 表示白色像素
- "1" 表示黑色像素
给定的黑色像素位置是 [0,2]
包含所有黑色像素的最小矩形是：
- 左边界：1
- 右边界：2
- 上边界：0
- 下边界：2
矩形面积为 (2-1+1) * (2-0+1) = 6示例 2：
输入：image = [["1"]], x = 0, y = 0
输出：1提示
- 1 <= image.length, image[0].length <= 100
- image[i][j] 为 ‘0’ 或 ‘1’
- 0 <= x < image.length
- 0 <= y < image[0].length
- image[x][y] == ‘1’
- 输入数据保证至少存在一个黑色像素
解题思路
本题可以使用两种方法来实现：
-
暴力搜索法：
- 遍历整个矩阵找到边界
- 记录最左、最右、最上、最下的黑色像素位置
- 计算矩形面积
- 时间复杂度O(mn)
-
二分查找法：
- 利用黑色像素的连续性
- 二分查找每一行和每一列的边界
- 优化搜索范围
- 时间复杂度O(mlogn + nlogm)
图解思路
边界搜索分析表
| 边界 | 搜索方向 | 判断条件 | 更新方式 |
|---|---|---|---|
| 左边界 | 从左到右 | 存在黑色像素 | 取最小列号 |
| 右边界 | 从右到左 | 存在黑色像素 | 取最大列号 |
| 上边界 | 从上到下 | 存在黑色像素 | 取最小行号 |
| 下边界 | 从下到上 | 存在黑色像素 | 取最大行号 |
二分查找步骤表
| 步骤 | 操作 | 目的 | 复杂度 |
|---|---|---|---|
| 1 | 确定搜索范围 | 限定边界 | O(1) |
| 2 | 二分查找左右边界 | 找到水平范围 | O(mlogn) |
| 3 | 二分查找上下边界 | 找到垂直范围 | O(nlogm) |
| 4 | 计算面积 | 得到最终结果 | O(1) |
代码实现
C# 实现
public class Solution {
public int MinArea(char[][] image, int x, int y) {
int m = image.Length;
int n = image[0].Length;
// 二分查找左边界
int left = BinarySearchLeft(image, 0, y, true);
// 二分查找右边界
int right = BinarySearchRight(image, y, n - 1, true);
// 二分查找上边界
int top = BinarySearchLeft(image, 0, x, false);
// 二分查找下边界
int bottom = BinarySearchRight(image, x, m - 1, false);
return (right - left + 1) * (bottom - top + 1);
}
private int BinarySearchLeft(char[][] image, int start, int end, bool searchColumn) {
while (start < end) {
int mid = start + (end - start) / 2;
if (HasBlackPixel(image, mid, searchColumn)) {
end = mid;
} else {
start = mid + 1;
}
}
return start;
}
private int BinarySearchRight(char[][] image, int start, int end, bool searchColumn) {
while (start < end) {
int mid = start + (end - start + 1) / 2;
if (HasBlackPixel(image, mid, searchColumn)) {
start = mid;
} else {
end = mid - 1;
}
}
return start;
}
private bool HasBlackPixel(char[][] image, int index, bool searchColumn) {
if (searchColumn) {
for (int i = 0; i < image.Length; i++) {
if (image[i][index] == '1') {
return true;
}
}
} else {
for (int j = 0; j < image[0].Length; j++) {
if (image[index][j] == '1') {
return true;
}
}
}
return false;
}
}Python 实现
class Solution:
def minArea(self, image: List[List[str]], x: int, y: int) -> int:
m, n = len(image), len(image[0])
def has_black_pixel(index: int, search_column: bool) -> bool:
if search_column:
return any(image[i][index] == '1' for i in range(m))
return any(image[index][j] == '1' for j in range(n))
def binary_search_left(start: int, end: int, search_column: bool) -> int:
while start < end:
mid = start + (end - start) // 2
if has_black_pixel(mid, search_column):
end = mid
else:
start = mid + 1
return start
def binary_search_right(start: int, end: int, search_column: bool) -> int:
while start < end:
mid = start + (end - start + 1) // 2
if has_black_pixel(mid, search_column):
start = mid
else:
end = mid - 1
return start
left = binary_search_left(0, y, True)
right = binary_search_right(y, n - 1, True)
top = binary_search_left(0, x, False)
bottom = binary_search_right(x, m - 1, False)
return (right - left + 1) * (bottom - top + 1)C++ 实现
class Solution {
public:
int minArea(vector<vector<char>>& image, int x, int y) {
int m = image.size();
int n = image[0].size();
// 二分查找左边界
int left = binarySearchLeft(image, 0, y, true);
// 二分查找右边界
int right = binarySearchRight(image, y, n - 1, true);
// 二分查找上边界
int top = binarySearchLeft(image, 0, x, false);
// 二分查找下边界
int bottom = binarySearchRight(image, x, m - 1, false);
return (right - left + 1) * (bottom - top + 1);
}
private:
bool hasBlackPixel(vector<vector<char>>& image, int index, bool searchColumn) {
if (searchColumn) {
for (int i = 0; i < image.size(); i++) {
if (image[i][index] == '1') {
return true;
}
}
} else {
for (int j = 0; j < image[0].size(); j++) {
if (image[index][j] == '1') {
return true;
}
}
}
return false;
}
int binarySearchLeft(vector<vector<char>>& image, int start, int end, bool searchColumn) {
while (start < end) {
int mid = start + (end - start) / 2;
if (hasBlackPixel(image, mid, searchColumn)) {
end = mid;
} else {
start = mid + 1;
}
}
return start;
}
int binarySearchRight(vector<vector<char>>& image, int start, int end, bool searchColumn) {
while (start < end) {
int mid = start + (end - start + 1) / 2;
if (hasBlackPixel(image, mid, searchColumn)) {
start = mid;
} else {
end = mid - 1;
}
}
return start;
}
};执行结果
C# 实现
- 执行用时：88 ms
- 内存消耗：38.4 MB
Python 实现
- 执行用时：36 ms
- 内存消耗：15.2 MB
C++ 实现
- 执行用时：4 ms
- 内存消耗：7.8 MB
性能对比
| 语言 | 执行用时 | 内存消耗 | 特点 |
|---|---|---|---|
| C# | 88 ms | 38.4 MB | 实现清晰，性能适中 |
| Python | 36 ms | 15.2 MB | 代码简洁，性能良好 |
| C++ | 4 ms | 7.8 MB | 性能最优，内存占用小 |
代码亮点
- 🎯 使用二分查找优化搜索效率
- 💡 巧妙处理边界条件
- 🔍 优化搜索方向和判断条件
- 🎨 代码结构清晰，复用性好
常见错误分析
- 🚫 边界条件处理不当
- 🚫 二分查找实现错误
- 🚫 搜索方向判断错误
- 🚫 面积计算错误
解法对比
| 解法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|
| 暴力搜索 | O(mn) | O(1) | 实现简单，直观 | 效率低 |
| 二分查找 | O(mlogn + nlogm) | O(1) | 效率高，优化好 | 实现复杂 |
相关题目
- LeetCode 74. 搜索二维矩阵 - 中等
- LeetCode 240. 搜索二维矩阵 II - 中等
- LeetCode 378. 有序矩阵中第K小的元素 - 中等
📖 系列导航
🔥 算法专题合集 - 查看完整合集
📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第302题。
💬 互动交流
感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。
如果这篇文章对你有帮助，请：
- 👍 点个赞，让更多人看到这篇文章
- 📁 收藏文章，方便后续查阅复习
- 🔔 关注作者，获取更多高质量算法题解
- 💭 评论区留言，分享你的解题思路或提出疑问
你的支持是我持续分享的动力！
💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！