Leetcode 最大正方形

java 实现

class Solution {public int maximalSquare(char[][] matrix) {//处理特殊情况if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;int rows = matrix.length;int cols = matrix[0].length;int[][] dp = new int[rows][cols]; //dp[i][j]的含义是以i,j为右下角的最大正方形边长int maxSide = 0; //maxSide是最大边长//遍历矩阵for(int i = 0; i < rows; i++) {for(int j = 0; j < cols; j++) {if(matrix[i][j] == '1') {if(i == 0 || j== 0) {dp[i][j] = 1; //第一行或第一列元素所能组成的最大正方形边长只能是1} else {//以当前位置为右下角的最大正方形边长可以通过当前位置左方,上方,左上方这三个位置为右下角的//最大正方形边长的最小值来确定dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;}// 更新最大边长maxSide = Math.max(maxSide, dp[i][j]);}}}return maxSide * maxSide;}
}