221. Maximal Square.md

title	toc	date	tags	top
221. Maximal Square	false	2017-10-30	Leetcode Dynamic Programming	221

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Example:

Input: 

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

Output: 4

分析

这道题目有点像LeetCode 53. Maximum Subarray。不过这道题目难了很多，从一维变成了二维，从连续子数组的最大和变成了连续矩阵的最大面积。应该来说，本质上没有发生变化，但是寻找对应的状态转移方程，难度大了许多。基本思路仿照Kadane's algorithm，也就是有maxEndingHere(i,j)记录到以$(i,j)$为右下角的最大矩阵，maxSoFar(i,j)记录从(0,0)到$(i,j)$的最大矩阵。

但是怎么求maxEndingHere(i, j)呢？一个$(i,j)$为右下角的最大矩阵，它的左边、右边、左上角肯定都是1。

dp(i, j) = min(dp(i−1, j), dp(i−1, j−1), dp(i, j−1)) + 1.

完整的Java代码

public int maximalSquare(char[][] matrix) {
    if (matrix == null) return 0;
    int m = matrix.length, n = m > 0 ? matrix[0].length : 0;
    int maxSquare = 0;  //maxSoFar
    int [][] dp = new int[m + 1][n + 1];  //maxEndingHere
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (matrix[i - 1][j - 1] == '1') {
                dp[i][j] = 1 +  Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]));
                if (dp[i][j] > maxSquare) maxSquare = dp[i][j];
            }
        }
    }
    return maxSquare*maxSquare;
}