题解 | #奶牛的活动面积# java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param land char字符型二维数组
     * @return int整型
     */
    public int maximalSquare (char[][] land) {
        // write code here
        int m = land.length;
        int n = land[0].length;
        int[][] f = new int[m][n];
        int ans = f[0][0] = (land[0][0] == 'C') ? 1 : 0;

        for (int i = 1; i < m; ++i) {
            f[i][0] = (land[i][0] == 'C') ? 1 : 0;
            ans = Math.max(ans, f[i][0]);
        }

        for (int j = 1; j < n; ++j) {
            f[0][j] = (land[0][j] == 'C') ? 1 : 0;
            ans = Math.max(ans, f[0][j]);
        }

        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                if (land[i][j] == 'C') {
                    f[i][j] = Math.min(f[i - 1][j], Math.min(f[i][j - 1], f[i - 1][j - 1])) + 1;
                    ans = Math.max(ans, f[i][j]);
                }
            }
        }

        return ans * ans;
    }
}

编程语言是Java。

该题考察的知识点包括：

• 动态规划：代码使用动态规划的思想，通过填表格的方式求解最大正方形的边长。

代码的文字解释：

1. 获取数组的行列数：获取数组的行数 m 和列数 n。
2. 创建状态数组：使用 int[][] f 来表示每个位置能够构成的最大正方形的边长。数组的大小为 m 行 n 列。
3. 初始化状态：将数组的第一行和第一列填充为 f[i][0] = (land[i][0] == 'C') ? 1 : 0; 和 f[0][j] = (land[0][j] == 'C') ? 1 : 0;，表示第一行和第一列能够构成的最大正方形边长。
4. 动态规划状态转移：遍历数组的其他位置 (i, j)，如果 land[i][j] 是 'C'，则 f[i][j] 取左边、上边、左上角位置的最小值加 1。这表示当前位置可以构成边长更大的正方形。
5. 更新最大正方形边长：在动态规划过程中，记录最大的 ans，它代表整个数组中最大正方形的边长。
6. 返回结果：返回 ans * ans，因为要求的是面积。