Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.
Example:
Input: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 Output: 4
题目大意：给定一个只包含0和1的二维二值矩阵，找到只包含1的最大正方形，并返回它的面积。
思路一：用一个临时变量a记录最大正方形的边长，遍历矩阵的每一个点(i,j), 另一个临时变量b记录以点(i,j)为左上角点的符合条件（全为1）的正方形的边长，如果b大于a，则更新a。
C++代码：
1 int maximalSquare(vector<vector<char>>& matrix) { 2 int rows = matrix.size(), colums = rows > 0 ? matrix[0].size() : 0; 3 int maxsqlen = 0; 4 for (int i = 0; i < rows; ++i) { 5 for (int j = 0; j < colums; ++j) { 6 //只有(i,j)为1，才有可能组成符合条件的正方形 7 if (matrix[i][j] == '1') { 8 int sqlen = 1; //从以（i,j）为左上角点的边长为sqlen = 1的正方形开始判断 9 bool flag = true; //记录边长为sqlen的正方形是否符合条件的 10 //判断以（i,j）为左上角点的边长为sqlen+1的正方形是否在matrix中，并且判断长为sqlen的正方形是否是符合条件的，如果不符合，那么同以(i,j)为左上角点，边长sqlen+1的正方形必然是不符合条件的 11 while (i + sqlen < rows && j + sqlen < colums && flag) { 12 //判断新的正方形的最后一行是否符合条件 13 for (int k = j; k <= sqlen + j; ++k) { 14 if (matrix[i + sqlen][k] == '0') { 15 flag = false; 16 break; 17 } 18 } 19 //判断新的正方形的最后一列是否符合条件 20 for (int k = i; k <= sqlen + i; ++k) { 21 if (matrix[k][j + sqlen] == '0') { 22 flag = false; 23 break; 24 } 25 } 26 //前两个循环结束判断，如果flag=ture,说明原来边长增长1的正方形仍然是符合条件的正方形。 27 if (flag) 28 sqlen++; 29 } 30 //结束前面循环后，sqlen为以（i,j）为左上角点的符合条件的最大正方形的边长，如果sqlen大于当前最大边长，则更新 31 if (maxsqlen < sqlen) { 32 maxsqlen = sqlen; 33 } 34 } 35 36 } 37 } 38 return maxsqlen * maxsqlen; 39 }
时间复杂度：$O((mn^)2)$
空间复杂度：$O(1)$
也可以考虑前序和，新开辟一个二维数组dp,大小和原矩阵相同，dp[i][j]的值表示以原矩阵(0,0)为左上角点，(i,j)为右下角点组成的矩形的和。
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + matrix[i][j]
记录完之后，当计算以(i,j)为左上角点长为sqlen时的正方形的和便可以直接得到，判断这个正方形是不是符合条件的，只要判断和是不是等于sqlen * sqlen.
1 int maximalSquare(vector<vector<char>>& matrix) { 2 int rows = matrix.size(), cols = rows > 0 ? matrix[0].size() : 0; 3 int maxsqlen = 0; 4 vector<vector<int> > dp(rows + 1, vector<int>(cols + 1, 0)); 5 for (int i = 1; i <= rows; ++i) { 6 for (int j = 1; j <= cols; ++j) { 7 dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + (matrix[i - 1][j - 1] - '0'); 8 } 9 } 10 for (int i = 0; i < rows; ++i) { 11 for (int j = 0; j < cols; ++j) { 12 for (int k = 0; k < min(rows - i, cols - j); ++k) { 13 int temp = dp[i + k + 1][j + k + 1] - dp[i][j + k + 1] - dp[i + k + 1][j] + dp[i][j]; 14 if (temp == (k + 1) * (k + 1)) { 15 maxsqlen = max(maxsqlen, temp); 16 } else { 17 break; 18 } 19 } 20 } 21 } 22 return maxsqlen; 23 }
思路二：（动态规划）
建立一个二维 dp 数组，其中 dp[i][j] 表示到达 (i, j) 位置所能组成的最大正方形的边长。我们首先来考虑边界情况，也就是当i或j为0的情况，那么在首行或者首列中，必定有一个方向长度为1，那么就无法组成长度超过1的正方形，最多能组成长度为1的正方形，条件是当前位置为1。对于任意一点 dp[i][j]，由于该点是正方形的右下角，所以该点的右边，下边，右下边都不用考虑，关心的就是左边，上边，和左上边。这三个位置的dp值 suppose 都应该算好的，还有就是要知道一点，只有当前 (i, j) 位置为1，dp[i][j] 才有可能大于0，否则 dp[i][j] 一定为0。当 (i, j) 位置为1，此时要看 dp[i-1][j-1], dp[i][j-1]，和 dp[i-1][j] 这三个位置，我们找其中最小的值，并加上1，就是 dp[i][j] 的当前值了。
1 int maximalSquare(vector<vector<char>>& matrix) { 2 int rows = matrix.size(), cols = rows > 0 ? matrix[0].size() : 0; 3 int maxsqlen = 0; 4 vector<vector<int> > dp(rows + 1, vector<int>(cols + 1, 0)); 5 for (int i = 1; i <= rows; ++i) { 6 for (int j = 1; j <= cols; ++j) { 7 if (matrix[i - 1][j - 1] == '1') { 8 dp[i][j] = min(min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]) + 1; 9 } 10 maxsqlen = max(maxsqlen, dp[i][j]); 11 } 12 } 13 return maxsqlen * maxsqlen; 14 }