题目描述
LeetCode原题链接：221. Maximal Square
Given an m x n binary matrix filled with 0‘s and 1‘s, find the largest square containing only 1‘s and return its area.
Example 1:
Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] Output: 4
Example 2:
Input: matrix = [["0","1"],["1","0"]] Output: 1
Example 3:
Input: matrix = [["0"]] Output: 0
Constraints:
m == matrix.lengthn == matrix[i].length1 <= m, n <= 300-
matrix[i][j]is‘0‘or‘1‘.
思路分析
这道题的Related Topic里有Dynamic Programming的标签，那我们就来看看动态规划思路的解法。
1）dp数组构造
我们遍历二维数组一般是按照从上到下、从左到右的顺序进行for循环。当到达一个新的位置(i,j)的时候，数组前 i 行和第 i+1 行前 j 列的位置都是已经遍历过了的。动态规划的核心就是用已知量去推导出未知量，所以(i,j)位置右面和下面的值是怎样无需关心，我们只要去关注上面和左面就可以了。那么，我们可以将当前访问的坐标当作某个可能存在的正方形的右下角，然后来看以该点为右下角的正方形可能的边长。由于只有1才可能组成正方形，当我们遇到0的时候，直接跳过就可以了。dp[m][n]表示一个与matrix矩阵相同大小的动态规划矩阵，dp[i][j]表示以(i,j)为正方形右下角时，存在的合法正方形中面积最大的那个正方形的边长。
当matrix[i][j]=0时，我们直接令dp[i][j]=0（以该位置为右下角的正方形不存在），当matrix[i][j]=1时，我们再进行后续计算。
2）寻找合法正方形
根据正方形的特性可知，可能存在的最大正方形的边长应该是 L = min(i, j)+1 ，我们可以把 L * L 区域当作一个搜寻范围。举个??，当遍历到(2,2)时，绿色框框表示以这样一个区域。如下图，这个区域内合法正方形的最大边长分别为3、2、1。
如果当前位置行号和列号不一样，比如下面的矩阵分别遍历到(1,2)、(2,3)、(2,1)的时候，这个绿色框框的范围和范围内合法正方形如下图，这些位置在dp数组中取值都是1。
显然，合法的正方形区域内所有值都应该是1。那么该怎么判断它们都是1呢？我们不可能每次都把搜寻区域从头到尾便利一遍去数1的个数是否是 边长*边长 个，这样做复杂度太高了！回顾dp[i][j]的定义它表示的是一个合法正方形的边长。我们来看看与(i,j)相邻的左上、上面、左面三个位置。下图灰色、蓝色和黄色区域分别表示以(i-1,j-1)、(i-1,j)、(i,j-1)为正方形右下角、最大正方形的面积范围。可以肯定，matrix矩阵中这些区域内的位置取值都是1。
我们把这三个方向的合法正方形区域合并到一起，它们交集范围内所有位置上的值都是1，再加上当前访问的(i,j)，正好可以填充成一个新的正方形。新的正方形的边长应该是min(dp[i][j-1], dp[i-1][], dp[i-1][j-1]) + 1。取最小值的目的是为了保证上、左、左上方向都满足值全是1的条件，否则可能会出现在某一方向不相邻位置上出现0的情况。
3）状态转移方程
从上面的分析我们可以看出，dp[i][j]的转移方程是一个关于dp[i-1][j]、dp[i][j-1]和dp[i-1][j-1]的式子。根据定义，后面的三个值有可能是0（表示无法构成合法正方形）或任何>=1的值。一旦这三个值中有一个是0，我们就无法生成一个新的正方形，dp[i][j]只能是一个最小单位即边长为1的正方形（前提是matrix[i][j] == 1）；当三个值都不为0时，可以生成一个新的正方形，它的边长是min(dp[i][j-1], dp[i-1][], dp[i-1][j-1]) + 1。两种情况的表达式可以合并。边界情况是第一行和第一列的位置，因为这些位置不具备三个方向上的全部分区，因此最多只能组成边长为1的合法正方形，对于这些位置dp的取值只需要判断当前位置是否是1就可以了。
综上，我们可以得到这道题的转移方程为：
然后，只需再用一个变量在遍历过程中记录最大的边长就可以得到结果啦！
代码示例（C++)
1 class Solution { 2 public: 3 int maximalSquare(vector<vector<char>>& matrix) { 4 int m = matrix.size(), n = matrix[0].size(), maxLength = 0; 5 vector<vector<int>> dp(m, vector<int>(n, 0)); 6 for(int i = 0; i < m; i++) { 7 for(int j = 0; j < n; j++) { 8 // 边界情况 9 if(i == 0 || j == 0) { 10 dp[i][j] = matrix[i][j] - ‘0‘; 11 } 12 else if(matrix[i][j] == ‘1‘){ 13 // 值为1的时候才有可能构成正方形 14 dp[i][j] = min(dp[i - 1][j - 1], min(dp[i][j - 1], dp[i - 1][j])) + 1; 15 } 16 // 记录当前最大边长 17 maxLength = max(maxLength, dp[i][j]); 18 } 19 } 20 return maxLength * maxLength; 21 } 22 };