221. Maximal Square

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

For example, given the following matrix:

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

Return 4.

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if(matrix.empty()||matrix[0].empty())
           return 0;
        int m = matrix.size();
        int n = matrix[0].size();
        
        vector<vector<int>> dp(m,vector<int>(n,0));
        int maxArea = 0;
        for(int i=0;i<m;i++)
        {
            dp[i][0] = matrix[i][0] - '0';
            maxArea = max(maxArea,dp[i][0]);
        }
        for(int j=0;j<n;j++)
        {
            dp[0][j] = matrix[0][j] - '0';
            maxArea = max(maxArea,dp[0][j]);
        }
        
        for(int i=1;i<m;i++)
          for(int j=1;j<n;j++)
          {
              if(matrix[i][j] == '1')
              {
                 dp[i][j] = min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]) + 1;
              }
              else
                 dp[i][j] = 0;
              maxArea = max(maxArea,dp[i][j]);
          }
        return maxArea*maxArea;
    }
};
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成,瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明:文章內(nèi)容(如有圖片或視頻亦包括在內(nèi))由作者上傳并發(fā)布,文章內(nèi)容僅代表作者本人觀點,簡書系信息發(fā)布平臺,僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容