Question

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

English Version

题目描述

图片在计算机处理中往往是使用二维矩阵来表示的。

给你一个大小为 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.length
• n == image[i].length
• 1 <= m, n <= 100
• image[i][j] 为 '0' 或 '1'
• 1 <= x < m
• 1 <= y < n
• image[x][y] == '1'
• image 中的黑色像素仅形成一个 组件

解法

方法一

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)

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);
  }
}

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);
  }
};

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)
}