【LeetCode】 221. Maximal Square

Description

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

給予一個二維的二元陣列，其元素只有0和1。找到由1構成的最大正方形並回傳它的面積。

Example:

Input: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4

Solution

• 先注意一件事情，他給的二元矩陣不是用int也不是bool，竟然是用char。(我沒注意到這個，找bug找好久QQ)
• 方法一是直接暴力破解，聽說可以過，但我沒有試過。
• 比較好的解法是使用DP。建一個表格，初始化和原來的矩陣一樣。
• 
  • 畫個圖來理解一下，當紅色都是1，藍色都是1，綠色也都是1時，如果右下角(黃色)也是1，就可以變成一個大的正方形。
• 
  • 換句話說，當左上、上、左都是x的時候，如果自己為1，就可以組成一個x + 1的正方形。
• 遞迴式：
  \[ DP[i][j] = \left\{\begin{matrix} min(DP[i-1][j],DP[i][j-1],DP[i-1][j-1]),m[i][j]=1 \\ 0,m[i][j]=0 \end{matrix}\right. \]
• 整理後可以發現，DP和原矩陣可以直接合併，最後時間複雜度為O(mn)，空間複雜度O(1)。

Code

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if(matrix.empty())
            return 0;
        int ans = 0;
        for(int i = 0; i < matrix.size(); i++)
        {
            for(int j = 0; j < matrix[0].size(); j++)
            {
                matrix[i][j] -= '0';
                if(i != 0 && j != 0 && matrix[i][j] == 1)
                    matrix[i][j] = min(min(matrix[i - 1][j], matrix[i][j - 1]), matrix[i - 1][j - 1]) + matrix[i][j];
                ans = ans < matrix[i][j] ? matrix[i][j] : ans;
            }
        }
        return ans * ans;
    }
};

tags: LeetCode C++