leetcode 221 Solution

代码解析

package com.demo.s221;

import java.util.HashMap;
import java.util.Map;

/**
 * 在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
 */
public class Solution {
public int maximalSquare(char[][] matrix) {
        int maxSide = 0;
        //判断 边界情况
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return maxSide;
        }
        int rows = matrix.length, columns = matrix[0].length;
        //新建一个dp二维数组
        int[][] dp = new int[rows][columns];
        for (int i = 0; i < rows; i++) {
        for (int j = 0; j < columns; j++) {
        //遇到1的情况 考虑动态转移方程
        if (matrix[i][j] == '1') {
        //边界的情况，初始化为1
        if (i == 0 || j == 0) {
        dp[i][j] = 1;
        } else {
        //左侧、上侧、左上侧 三个 最大值加1
        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]);
        }
        }
        }
        //计算面积
        int maxSquare = maxSide * maxSide;
        return maxSquare;
        }

        }