Problem: 221. 最大正方形

👨‍🏫 参考题解

class Solution {public int maximalSquare(char[][] matrix) {// base condition: 如果矩阵为空，直接返回面积为 0if (matrix == null || matrix.length < 1 || matrix[0].length < 1) {return 0;}int height = matrix.length;  // 获取矩阵的高度int width = matrix[0].length;  // 获取矩阵的宽度int maxSide = 0;  // 用于存储当前找到的最大正方形的边长// 创建 dp 数组，dp[i][j] 表示以 (i-1, j-1) 为右下角的正方形的最大边长// 这里的 dp 数组多一行和多一列，用来处理边界情况，避免复杂的 if 判断int[][] dp = new int[height + 1][width + 1];  // 遍历矩阵中的每个格子for (int row = 0; row < height; row++) {for (int col = 0; col < width; col++) {// 只有当前格子为 '1' 时，才能形成正方形if (matrix[row][col] == '1') {// 核心思路：如果当前格子是 '1'，且上、左、左上格子也是 '1'，// 那么以当前格为右下角的最大正方形边长// = 上、左、左上三个方向的最小边长 + 1。dp[row + 1][col + 1] = Math.min(Math.min(dp[row + 1][col], dp[row][col + 1]),  // 左、上dp[row][col]  // 左上) + 1;// 更新 maxSide，记录最大的边长maxSide = Math.max(maxSide, dp[row + 1][col + 1]);}}}// 最后返回最大正方形的面积，面积 = 边长 * 边长return maxSide * maxSide;}
}