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;
    }
};
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容