221. Maximal Square（最大的面积）-蒲公英云

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.
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;
    }
};