Leetcode面试经典150题-221.最大正方形

  解法都在代码里，不懂就留言或者私信

class Solution {/**本题一看就是典型的动态规划，要找以每个点为右下角的正方形的面积，然后取最大的这个题要注意找规律，我找到的规律如下：1.以第一行为右下角的，因为正方形是边长相同的，所以第一行为右下角最大正方形只能是自己，自己是1就是1，不是1就是02. 以第一列为右下角的也是一样。3. 以普通位置为右下角的最大正方形，首先看自己是不是1，如果自己不是1，那就肯定是0，如果自己是1，取它的左上、左、上三个点的最小面积,加1就是它的解自己可以多画几个二维矩阵找找规律*/public int maximalSquare(char[][] matrix) {/**空矩阵的校验，健壮性校验 */if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {return 0;}/**如果矩阵只有一个数字，那就是0最大面积就是0，是'1'最大面积就是1*/if(matrix.length == 1 && matrix[0].length == 1) {return matrix[0][0] == '1'? 1 : 0;}/**其他的不过多枚举了，直接动态规划解吧，dp[i][j]代表以(i,j)为右下角的最大正方形的边长*/int[][] dp = new int[matrix.length][matrix[0].length];/**定义最大值变量 */int maxArea = 0;/**初始化第一行和第一列*/for(int j = 0; j < dp[0].length; j++) {dp[0][j] = matrix[0][j] == '1'? 1 : 0;/**这里其实是dp[0][j]* dp[0][j]，反正最大就是1，懒得写了 */maxArea = Math.max(maxArea, dp[0][j]);}for(int i = 1; i < dp.length; i++) {dp[i][0] = matrix[i][0] == '1'? 1 : 0;/**这里其实是dp[i][0]* dp[i][0]，反正最大就是1，懒得写了 */maxArea = Math.max(maxArea, dp[i][0]);}/**初始化普通位置 */for(int i = 1; i < dp.length; i++) {for(int j = 1; j < dp[i].length; j++) {if(matrix[i][j] == '1') {dp[i][j] = matrix[i][j] == '1'? Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1 : 0;maxArea = Math.max(maxArea, dp[i][j]*dp[i][j]);}}}return maxArea;}
}

 相信我这就是最优解，矩阵就是m*n，你不过完能知道答案吗