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

樣例
For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 4.

解題思路
初始思路是判斷對(duì)角方向以及相鄰的兩個(gè)數(shù),運(yùn)行結(jié)果錯(cuò)誤，然后查看錯(cuò)誤發(fā)現(xiàn)需要判斷整個(gè)鄰邊，因此想到遍歷鄰邊判斷（i，j）位置的最大面積。但是會(huì)發(fā)現(xiàn)（i，j）之前的點(diǎn)的結(jié)果已經(jīng)得出，為什么會(huì)重復(fù)用到之前的點(diǎn)，整個(gè)過程應(yīng)該可以優(yōu)化。思考后想到了同時(shí)三個(gè)方向判斷，因此得出轉(zhuǎn)移方程：maxArea[i][j] = Math.min(maxArea[i][j - 1],Math.min(maxArea[i - 1][j - 1], maxArea[i - 1][j])) + 1；

錯(cuò)誤代碼

    if(matrix[i - 1][j] == 1 && matrix[i][j - 1] == 1 && matrix[i - 1][j - 1] == 1)
    {
           maxArea[i][j] = maxArea[i - 1][j - 1] + 1;
       if(maxArea[i][j] > maxResultArea)
       {
              maxResultArea = maxArea[i][j];
       }
    }           

正確代碼

public class Solution {
    /**
     * @param matrix: a matrix of 0 and 1
     * @return: an integer
     */
  public int maxSquare(int[][] matrix) {
        if(null == matrix)
        {
            return 0;
        }
        int row = matrix.length;
        if(row <= 0)
        {
            return 0;
        }
        int col = matrix[0].length;
        int[][] maxArea = new int[row][col];
        int maxResultArea = Integer.MIN_VALUE;
        
        for(int i = 0;i < row;i++)
        {
            maxArea[i][0] = matrix[i][0];
            if(maxArea[i][0] > maxResultArea)
            {
                maxResultArea = maxArea[i][0];
            }
        }
        
        for(int i = 0;i < col;i++)
        {
            maxArea[0][i] = matrix[0][i];
            if(maxArea[0][i] > maxResultArea)
            {
                maxResultArea = maxArea[0][i];
            }
        }
        
        for(int i = 1;i < row;i++)
        {
            for(int j = 1;j < col;j++)
            {
                if(matrix[i][j] == 1)
                {
                    maxArea[i][j] = Math.min(maxArea[i][j - 1],Math.min(maxArea[i - 1][j - 1], maxArea[i - 1][j])) + 1;
                }
                if(maxArea[i][j] > maxResultArea)
                {
                    maxResultArea = maxArea[i][j];
                }
            }
        }
        return maxResultArea > 0 ?  maxResultArea * maxResultArea : 0;
    }
}