leetcode 221. 最大正方形

题目描述：

在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。

思路分析：

一道动态规划的题。由于是正方形，首先单一的‘1’即为最小的正方形，接下来需要考察其外围区域是否为1。具体来说，dp[i][j]表示包含该点的最大正方形的边长。同时不断去更新这个最大边长。这里的递推是从前向后，如dp[i][j]=1，那么需要看dp[i-1][j]，dp[i][j-1]以及dp[i-1][j-1]三个部分，动态递推公式为dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])+1，更新最大边长。需要注意两个边界，即第一行和第一列，直接判断01，赋值即可。

代码：

 class Solution {

 public:

     int maximalSquare(vector<vector<char>>& matrix) {

         int row = matrix.size();

         if(row == )

             return ;

         int col = matrix[].size();

         vector<vector<int>> res(row, vector<int>(col, ));

         int maxval = ;

         for(int i=; i<row; i++)

         {

             res[i][] = matrix[i][]-'';

             maxval = max(maxval, res[i][]);

         }

         for(int i=; i<col; i++)

         {

             res[][i] = matrix[][i]-'';

             maxval = max(maxval, res[][i]);

         }

         for(int i=; i<row; i++)

         {

             for(int j=; j<col; j++)

             {

                 if(matrix[i][j] == '')

                     res[i][j] = ;

                 else

                 {

                     res[i][j] = min(res[i-][j-], min(res[i-][j], res[i][j-]))+;

                     maxval = max(maxval, res[i][j]);

                 }

             }

         }

         return maxval*maxval;

     }

 };

巴特西

leetcode 221. 最大正方形

最新文章

热门文章