题目：
Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area.
For example, given the following matrix:
1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0
Return 4.
链接：
题解：
二维DP，先初始化首行和首列，然后假设matrix[i][j] == '1'，我们可以先设定dp[i][j] = 1，然后根据左上，上，左三个元素中最小的一个来求新的值。代码写得较繁琐，还可以优化空间复杂度。
Time Complexity - O(n2)， Space Complexity - O(n2)
public class Solution { public int maximalSquare(char[][] matrix) { if(matrix == null || matrix.length == 0) return 0; int[][] dp = new int[matrix.length][matrix[0].length]; int max = 0; for(int i = 0; i < matrix.length; i++) { if(matrix[i][0] == '1') { dp[i][0] = 1; if(max == 0) max = 1; } } for(int j = 0; j < matrix[0].length; j++) { if(matrix[0][j] == '1') { dp[0][j] = 1; if(max == 0) max = 1; } } for(int i = 1; i < dp.length; i++) { for(int j = 1; j < dp[0].length; j++) { if(matrix[i][j] == '1') { dp[i][j] = 1; if(dp[i - 1][j - 1] > 0 && dp[i - 1][j] > 0 && dp[i][j - 1] > 0) { int prev = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])); prev = (int)Math.sqrt(prev) + 1; prev *= prev; dp[i][j] = prev; max = Math.max(max, prev); } } } } return max; }}
二刷:
使用了与一刷相同的方法, 二维dp。先初始化dp矩阵行和列，再根据当前点上边，左边，左上边的三个点来决定是否是一个全一square，假如是一个全一square，那么我们还要根据这三个点里的最小值来求出当前点的值，要先开方，加1再平方。代码繁琐，速度也比较慢，说明功力还不足。这里dp[i][j]是全一正方形的元素数，这个设置并不好。
Java:
2D - DP
Time Complexity - O(mn)， Space Complexity - O(mn)
public class Solution { public int maximalSquare(char[][] matrix) { if (matrix == null || matrix.length == 0) { return 0; } int rowNum = matrix.length; int colNum = matrix[0].length; int[][] dp = new int[rowNum][colNum]; int max = 0; for (int i = 0; i < rowNum; i++) { if (matrix[i][0] == '1') { dp[i][0] = 1; max = 1; } } for (int j = 0; j < colNum; j++) { if (matrix[0][j] == '1') { dp[0][j] = 1; max = 1; } } for (int i = 1; i < rowNum; i++) { for (int j = 1; j < colNum.length; j++) { if (matrix[i][j] == '1') { dp[i][j] = 1; if (dp[i - 1][j - 1] > 0 && dp[i - 1][j] > 0 && dp[i][j - 1] > 0) { int prev = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])); prev = (int)Math.sqrt(prev) + 1; dp[i][j] = prev * prev; } max = Math.max(dp[i][j], max); } } } return max; }}
二维dp改进，我们改变dp[i][j]的设置，下面dp[i][j]代表以(i, j)为右下角的全一矩阵的最长边长，这样我们就可以避免每次计算sqrt以及作乘法， 只要最后返回maxLen * maxLen就可以了。速度从18%上升到了58%。
public class Solution { public int maximalSquare(char[][] matrix) { if (matrix == null || matrix.length == 0) { return 0; } int rowNum = matrix.length; int colNum = matrix[0].length; int[][] dp = new int[rowNum][colNum]; int maxLen = 0; for (int i = 0; i < rowNum; i++) { if (matrix[i][0] == '1') { dp[i][0] = 1; maxLen = 1; } } for (int j = 0; j < colNum; j++) { if (matrix[0][j] == '1') { dp[0][j] = 1; maxLen = 1; } } for (int i = 1; i < rowNum; i++) { for (int j = 1; j < colNum; j++) { if (matrix[i][j] == '1') { dp[i][j] = 1; if (dp[i - 1][j - 1] > 0 && dp[i - 1][j] > 0 && dp[i][j - 1] > 0) { dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1; } maxLen = Math.max(dp[i][j], maxLen); } } } return maxLen * maxLen; }}
一维DP：
这里因为dp[i][j]的值只和dp[i - 1][j - 1], dp[i - 1][j]以及dp[i][j - 1]相关，所以我们可以使用滚动数组来进行空间复杂度的优化，一行一行进行计算。思路大都借鉴了jianchao.li.figher大神的。我们先遍历首行和首列查找元素'1'，假如有'1'则max可以设置为1。接下来使用了一个临时变量topLeft来保存topLeft元素，在matrix[i][j] == '1'的情况下，在滚动数组里我们仍然考虑左边元素 - dp[j - 1]， 上方元素dp[j]以及左上元素topLeft。 我们预先保存dp[j]作为下一次计算的topLeft。 最后返回 maxLen * maxLen。
还要继续精炼代码。看过dietpepsi乐神的代码以后发现真是简短而且优美。
Time Complexity - O(mn)， Space Complexity - O(n)
public class Solution { public int maximalSquare(char[][] matrix) { if (matrix == null || matrix.length == 0) { return 0; } int rowNum = matrix.length; int colNum = matrix[0].length; int[] dp = new int[colNum]; int maxLen = 0; for (int j = 0; j < colNum; j++) { if (matrix[0][j] == '1') { dp[j] = 1; maxLen = 1; } } if (maxLen == 0) { for (int i = 0; i < rowNum; i++) { if (matrix[i][0] == '1') { maxLen = 1; break; } } } int topLeft = 0; for (int i = 1; i < rowNum; i++) { for (int j = 1; j < colNum; j++) { if (j == 1) { topLeft = matrix[i - 1][j - 1] - '0'; dp[j - 1] = matrix[i][j - 1] - '0'; } int tmp = dp[j]; if (matrix[i][j] == '1') { if (dp[j] > 0 && dp[j - 1] > 0 && topLeft > 0) { dp[j] = Math.min(dp[j - 1], Math.min(dp[j], topLeft)) + 1; } else { dp[j] = 1; } maxLen = Math.max(dp[j], maxLen); } else { dp[j] = 0; } topLeft = tmp; } } return maxLen * maxLen; }}
一维DP的优化：
- 扩大初始化dp数组的size到colNum + 1，这样我们就不需要对首行和首列进行额外地判断。只需要在每次j = 1的时候设置dp[j - 1] = 0，以及topLeft = 0就可以了。代码还是不太好看，还可以继续优化代码。
public class Solution { public int maximalSquare(char[][] matrix) { if (matrix == null || matrix.length == 0) { return 0; } int rowNum = matrix.length; int colNum = matrix[0].length; int[] dp = new int[colNum + 1]; int maxLen = 0; int topLeft = 0; for (int i = 1; i <= rowNum; i++) { for (int j = 1; j <= colNum; j++) { if (j == 1) { topLeft = 0; dp[j - 1] = 0; } int tmp = dp[j]; if (matrix[i - 1][j - 1] == '1') { if (dp[j] > 0 && dp[j - 1] > 0 && topLeft > 0) { dp[j] = Math.min(dp[j - 1], Math.min(dp[j], topLeft)) + 1; } else { dp[j] = 1; } maxLen = Math.max(maxLen, dp[j]); } else { dp[j] = 0; } topLeft = tmp; } } return maxLen * maxLen; }}
一维DP再优化:
下面又作了一些优化:
- 去除了 j == 1的判断，因为上面扩大了一维dp数组的size，所以dp[0]总是等于0
- 把topLeft的定义放在了外循环， 我们在处理每行之前，设置int topLeft = 0
- 简化了当matrix[i - 1][j - 1] == '1'时的逻辑。我们不需要判断左上，上和左三个点是否大于0， 只需要取三个点的min 再加1就可以了
到这里已经比较接近discuss里jianchao.li.fighter的版本了。 我们还可以把i 从 0 ~ rowNum进行遍历，这样就少作一个 i - 1的计算。那就基本和jianchao.li.fighter的解一样了。
public class Solution { public int maximalSquare(char[][] matrix) { if (matrix == null || matrix.length == 0) { return 0; } int rowNum = matrix.length, colNum = matrix[0].length; int[] dp = new int[colNum + 1]; int maxLen = 0; for (int i = 1; i <= rowNum; i++) { int topLeft = 0; for (int j = 1; j <= colNum; j++) { int tmp = dp[j]; if (matrix[i - 1][j - 1] == '1') { dp[j] = Math.min(dp[j - 1], Math.min(dp[j], topLeft)) + 1; maxLen = Math.max(maxLen, dp[j]); } else { dp[j] = 0; } topLeft = tmp; } } return maxLen * maxLen; }}
二维DP再优化
public class Solution { public int maximalSquare(char[][] matrix) { if (matrix == null || matrix.length == 0) { return 0; } int rowNum = matrix.length, colNum = matrix[0].length; int[][] dp = new int[rowNum + 1][colNum + 1]; int maxLen = 0; for (int i = 1; i <= rowNum; i++) { for (int j = 1; j <= colNum; j++) { if (matrix[i - 1][j - 1] == '1') { dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1; maxLen = Math.max(maxLen, dp[i][j]); } } } return maxLen * maxLen; } }
三刷:
Java:
二维dp
public class Solution { public int maximalSquare(char[][] matrix) { if (matrix == null || matrix.length == 0) return 0; int rowNum = matrix.length, colNum = matrix[0].length; int[][] dp = new int[rowNum + 1][colNum + 1]; int minLen = 0; for (int i = 1; i <= rowNum; i++) { for (int j = 1; j <= colNum; j++) { if (matrix[i - 1][j - 1] == '1') { dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])); minLen = Math.max(minLen, dp[i][j]); } } } return minLen * minLen; }}
简化为一维dp:
主要还是使用了topLeft来代表左上角的值。要注意先用tmp保存当前dp[j]，结束完这个位置的计算时更新topLeft。在每一行开始前充值topLeft = 0。还有就是matrix[i - 1][j - 1] = '0'的情况下我们要设置dp[j] = 0
public class Solution { public int maximalSquare(char[][] matrix) { if (matrix == null || matrix.length == 0) return 0; int rowNum = matrix.length, colNum = matrix[0].length; int[] dp = new int[colNum + 1]; int minLen = 0; for (int i = 1; i <= rowNum; i++) { int topLeft = 0; for (int j = 1; j <= colNum; j++) { int tmp = dp[j]; if (matrix[i - 1][j - 1] == '1') { dp[j] = 1 + Math.min(topLeft, Math.min(dp[j], dp[j - 1])); minLen = Math.max(minLen, dp[j]); } else { dp[j] = 0; } topLeft = tmp; } } return minLen * minLen; }}
Reference:
https://leetcode.com/discuss/63211/java-8ms-python-112-ms-dp-solution-o-mn-time-one-pass
http://www.cnblogs.com/jcliBlogger/p/4548751.html
https://leetcode.com/discuss/38489/easy-solution-with-detailed-explanations-8ms-time-and-space