題目資訊

• 題目編號: 302
• 題目連結: Smallest Rectangle Enclosing Black Pixels
• 主題: Array, Binary Search, Depth-First Search, Breadth-First Search, Matrix

題目敘述

您被給予一個 $m \times n$ 的二元矩陣圖像，其中 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 == \text{image.length}$
• $n == \text{image}[i].\text{length}$
• $1 \leq m, n \leq 100$
• $\text{image}[i][j]$ 是 '0' 或 '1'。
• $0 \leq x < m$
• $0 \leq y < n$
• $\text{image}[x][y] == ‘1’.$
• 圖像中的黑色像素只形成一個組件。

直覺

這個問題的核心在於確定能包圍給定二進制矩陣中所有黑色像素的最小軸對齊矩形的面積。這些黑色像素形成一個單一的連通區域，意味著它們在水平方向或垂直方向上是相連的。鑒於矩陣的尺寸可以達到 $100 \times 100$，因此需要有效地確定黑色區域的邊界以計算面積。

解法

解法涉及遍歷二進制矩陣以找到黑色像素的最小和最大坐標，這將決定矩形的邊界。具體來說，我們將：

1. 初始化邊界變量 up、down、left 和 right 為其相應的極端值。up 被初始化為行數減一（m - 1），down 為零，left 為列數減一（n - 1），right 为零。這些變量會隨著更多黑色像素被發現而更新。

2. 使用兩個巢狀的迴圈遍歷矩陣中的每一個單元。外部迴圈遍歷行，而內部迴圈遍歷列。

3. 對於每一個單元，檢查像素是否為黑色（'1'）。如果是，則更新邊界：

   • up 被更新為其當前值和當前行索引 i 中較小的值。
   • down 被更新為其當前值和當前行索引 i 中較大的值。
   • left 被更新為其當前值和當前列索引 j 中較小的值。
   • right 被更新為其當前值和當前列索引 j 中較大的值。

4. 完成遍歷後，最小的包圍矩形將在 (up, left) 到 (down, right) 之間。

5. 矩形的面積可以通過以下公式計算： $$\text{面積} = (down - up + 1) \times (right - left + 1)$$ 這將給出能包圍所有黑色像素的最小矩形的像素數目。

最終，這個實施方案在符合限制條件下有效計算所需的面積，因為循環一起以 $O(m \cdot n)$ 的時間複雜度覆蓋整個矩陣。

程式碼

C++

class Solution {
public:
    int minArea(vector<vector<char>>& image, int x, int y) {
        int m = image.size(); // 圖片的行數
        int n = image[0].size(); // 圖片的列數
        
        // 初始化黑色像素區域的邊界
        int up = m - 1, down = 0, left = n - 1, right = 0;
        
        // 遍歷整個矩陣以找到黑色區域的邊界
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (image[i][j] == '1') { // 如果該像素是黑色
                    up = min(up, i);   // 更新上邊界
                    down = max(down, i); // 更新下邊界
                    left = min(left, j); // 更新左邊界
                    right = max(right, j); // 更新右邊界
                }
            }
        }
        
        // 計算並返回包圍矩形的面積
        return (down - up + 1) * (right - left + 1);
    }
};

Python

class Solution:
    def minArea(self, image: List[List[str]], x: int, y: int) -> int:
        m = len(image)  # 圖片的行數
        n = len(image[0])  # 圖片的列數

        # 初始化黑色像素區域的邊界
        up = m - 1
        down = 0
        left = n - 1
        right = 0

        # 遍歷整個矩陣以找到黑色區域的邊界
        for i in range(m):
            for j in range(n):
                if image[i][j] == '1':  # 如果像素為黑色
                    up = min(up, i)  # 更新上邊界
                    down = max(down, i)  # 更新下邊界
                    left = min(left, j)  # 更新左邊界
                    right = max(right, j)  # 更新右邊界

        # 計算並返回包圍矩形的面積
        return (down - up + 1) * (right - left + 1)

複雜度分析

• 時間複雜度: $O(m \times n)$
  該解決方案遍歷整個 $m \times n$ 的矩陣以確定黑色像素區域的邊界。它精確地檢查矩陣中的每個元素一次，導致時間複雜度為 $O(m \times n)$。

• 空間複雜度: $O(1)$
  空間複雜度為 $O(1)$，因為該解決方案使用固定數量的額外空間，與輸入矩陣的大小無關。用於存儲邊界（up、down、left、right）和循環計數器的變量不會隨著輸入大小進行縮放。