题目描述
在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵char[][] matrix内，找到只包含 ‘1’ 的最大正方形，并返回其面积。
解题思路
思路1:穷举遍历整个数组
思路2: 动态规划，利用已遍历位置信息来加速查询。
新建一个数组sequare[][] 表示已当前位置i,j 为右下角的正方形的边长。
递推公式：
sequare[i][j] =Math.min(sequare[i][j-1] + sequare[i-1][j-1] + sequare[i-1][j]）+ 1；
代码实现
依据思路二实现算法如下
class Solution {public int maximalSquare(char[][] matrix) {int res = 0;int[][] len = new int[matrix.length][matrix[0].length];for (int i = 0; i < matrix.length; i++) {if (matrix[i][0] == '1') {len[i][0] = 1;res = 1;}}for (int i = 0; i < matrix[0].length; i++) {if (matrix[0][i] == '1') {len[0][i] = 1;res = 1;}}for (int i = 1; i < matrix.length; i++) {for (int j = 1; j < matrix[0].length; j++) {if (matrix[i][j] == '1') {len[i][j] = Math.min(len[i - 1][j - 1], Math.min(len[i - 1][j], len[i][j - 1])) + 1;res = Math.max(res, len[i][j]);}}}return res * res;}
}
