LeetCode 221. Maximal Square

Problem

LeetCode 221. Maximal Square

1. 题目简述

给出一个二维矩阵由0和1组成，找出其中最大的由1组成的最大正方形的面积。例如：

Input: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4

2. 算法思路

相关问题：

1. LeetCode 85. Maximal Rectangle

这道题的变种，85题和这道题的思路完全不同，强烈建议重新看一下。而且85题的dp思路极其难懂，用的方法很不一样。

DP

其实这道题也是用画图的方式来解决的。其实让我们找出最大的正方形面积，其实也就是找到最大的正方形边长。我们用一个dp值来记录，以当前位置为右下角的最大的正方形边长。假如说我们遍历到某个点(i, j)为1时（为0的时候不可能为正方形），那么以它为右下角的正方形的边长满足如下递推式：

$$dp[i][j] = min (dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1$$

记录全局的最大边长。遍历结束后计算出面积即可。

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

        // dp[i][j]表示以[i][j]为右下角的正方形最大的边长，记得找一个全局最长的边即可。
        // 这里dp可以转化为一维！
        int m = matrix.length, n = matrix[0].length, maxEdge = 0;
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (matrix[i - 1][j - 1] == '1') {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    maxEdge = Math.max(dp[i][j], maxEdge);
                }
            }
        }

        return maxEdge * maxEdge;
    }
}