221. Maximal Square（最大的面积）

我会带着你远行 2023-07-25 09:06 14阅读 0赞

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.  
Input:  
1 0 1 0 0  
1 0 1 1 1  
1 1 1 1 1  
1 0 0 1 0  
Output: 4  
思路：  
动态规划，记录dp\[ i\] \[ j \] 为以这个点为右下角的正方形，获取dp(i,j)是通过找到dp(i-1,j) 和dp （i，j-1）与 dp（j-1，j-1）的**最小值**，\*\*（前提是将第一行和第一列弄好0/1， 为之后的避免越界！）\*\*为什么是最小值呢？因为这样才能最少的来满足每个点都有：变为正方形。本来是需要一个矩阵的，但是因为只需要记录左，上，左上三个点的值，两行就够了。然后再将上一行填充0，两行再交换。再继续填充下一行。每弄一个求一个maxnum。

代码：

class Solution { 
    public:
        int maximalSquare(vector<vector<char>>& matrix) { 
            if(matrix.size()==0)
                return 0;
            int n=matrix.size(),m=matrix[0].size(), sz=0;
            vector<int> pre(m,0),cur(m,0);
            for(int i=0;i<n;++i)
            { 
                for(int j=0;j<m;++j)
                { 
                    if(matrix[i][j]=='0' || !i ||  !j  )
                        cur[j]=matrix[i][j]-'0';                //先将第一行第一列全设置好，防止越界。
                    else
                    { 
                        cur[j]=min( pre[j],  min( cur[j-1], pre[j-1]))  +1;  //为啥是最小值取出来。因为这样可以将三个点平均下来
                    }
                    sz=max(cur[j],sz);
                }
                fill(pre.begin(), pre.end(),0);
                swap(pre,cur);              //为了只用两行解决掉
             }
            return sz*sz;
        }
    };