#221最大正方形

final class Solution {
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }

        int rows = matrix.length;
        int columns = matrix[0].length;
        int[][] dp = new int[rows][columns];
        int maximumSide = 0;
        for (int row = 0; row < rows; row++) {
            for (int column = 0; column < columns; column++) {
                // 只有字符 1 才可能作为全 1 正方形的右下角。
                if (matrix[row][column] != '1') continue;
                if (row == 0 || column == 0) {
                    // 第一行或第一列最多形成边长为 1 的正方形。
                    dp[row][column] = 1;
                } else {
                    // 边长受左、上、左上三个相邻正方形中的最短边限制。
                    dp[row][column] = 1 + Math.min(
                        dp[row - 1][column - 1],
                        Math.min(dp[row - 1][column], dp[row][column - 1])
                    );
                }
                maximumSide = Math.max(maximumSide, dp[row][column]);
            }
        }
        // DP 记录的是边长，题目要求返回面积。
        return maximumSide * maximumSide;
    }
}