力扣221——最大正方形

这道题主要是利用动态规划，注意好边界条件，就可以解决。

原题

在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。

示例:

原题url：https://leetcode-cn.com/problems/maximal-square/

解题

动态规划

这道题应该很快会让我们想起使用动态规划，从左上角往右下角开始找。

假设我们用一个二维数组dp，记录每一个位置所能构成的最大正方形的边长（从左上角开始算）。位置(i, j)是 1，则其可能构成的正方形的边长是Min(dp(i - 1, j - 1), dp(i - 1, j), dp(i, j - 1)) + 1。看到这个，相信你也会理解了，每一个位置所能构成的最大边长的条件，其实是要求包围着它的左上角三个位置都是 1 才可以。

一直递推回到最初点，也就意味着，第一行和第一列需要单独判断。

之前应该也有做过类似空间复杂度上的优化，我们真的需要一个真正的二维数据dp来记录中间结果吗？其实我们发现，当一个位置用过之后，这个位置本身的数字已经不再重要，关键是该位置所能构成的最大正方形的边长，也就是我们记录的中间结果。因此可以直接更新原数组上的数字。

还有就是需要考虑一些特殊情况，比如只有一行或者一列的时候，我们应该如何做。

接下来让我们看看代码：

class Solution {
    public int maximalSquare(char[][] matrix) {
        // 高
        int height = matrix.length;
        if (height == 0) {
            return 0;
        }
        // 宽
        int width = matrix[0].length;

        // 检查第一行和第一列，是否有'1'
        int result = checkFirstRowAndCol(matrix, height, width);
        // 只有一行或一列，或者只有一个
        if (height == 1 || width == 1) {
            return result;
        }

        // result现在做为记录最大边的长度
        // 中间结果
        int temp;
        for (int i = 1; i < height; i++) {
            for (int j = 1; j < width; j++) {
                if (matrix[i][j] == '0') {
                    continue;
                }

                // 求出matrix[i - 1][j - 1]、matrix[i - 1][j]、matrix[i][j - 1]中的最小值
                temp = matrix[i - 1][j] < matrix[i][j - 1] ? matrix[i - 1][j] : matrix[i][j - 1];
                temp = temp < matrix[i - 1][j - 1] ? temp : matrix[i - 1][j - 1];
                // 更新当前节点的值
                matrix[i][j] = (char) (temp + 1);
                temp = temp + 1 - '0';

                if (result < temp) {
                    result = temp;
                }
            }
        }

        return result * result;
    }

    private int checkFirstRowAndCol(char[][] matrix, int height, int width) {
        // 检查第一列
        for (int i = 0; i < height; i++) {
            if (matrix[i][0] == '1') {
                return 1;
            }
        }

        // 检查第一行
        for (int i = 0; i < width; i++) {
            if (matrix[0][i] == '1') {
                return 1;
            }
        }

        return 0;
    }
}