最大正方形

简书来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximal-square

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

示例:

输入:

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

输出: 4

动态规划解法：

class Solution {

    class Node{
        int x;
        int y;
        int area;
    }

    public int maximalSquare(char[][] matrix) {
        if(matrix.length == 0)
            return 0;
        Node[][] dp = new Node[matrix.length][matrix[0].length];
        int ans = 0;
        for(int i=0;i<matrix.length;i++){
            for(int j=0;j<matrix[0].length;j++){
                Node node = new Node();
                if(matrix[i][j] == '1'){
                    node.x = j==0?1:dp[i][j-1].x+1;
                    node.y = i==0?1:dp[i-1][j].y+1;
                    if(i == 0||j==0){
                        node.area = 1;
                    }else{
                        //左上角
                        Node tmpNode = dp[i-1][j-1];
                        if(tmpNode.area == 0){
                            node.area = 1;
                        }else{
                            //左上角面积大于0
                            //左上角正方形的宽度
                            int width = (int)Math.sqrt(tmpNode.area);
                            if(node.x > width && node.y > width){
                                //当前节点的长宽大于左上角
                                node.area = (width+1)*(width+1);
                            }else{
                                //找出短的一条边
                                int min = Math.min(node.x,node.y);
                                node.area = min*min; 
                            }
                        }
                    }
                }
                dp[i][j] = node;
                ans = Math.max(ans,node.area);
            }
        }
        return ans;
    }
}