最大正方形

题目

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

示例:
输入:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
输出: 4

解题思路

有三个比较关键的点，判断某个点可形成的最大矩形，可以通过获得已经求得的三个点来得出结果
分别是左侧，上方，左上方。

1. dp的状态用来储存当前位置可用的最大宽度（通过以上三个点求得）
2. dp转移方程为常用的模板：

if (grid(i, j) == 1) {
    dp(i, j) = min(dp(i-1, j), dp(i, j-1), dp(i-1, j-1)) + 1; //因为是最大正方形，所以长宽的最小值才能满足结果。
}

3. 用maxWidth不断求得最大宽度。
4. maxWidth *maxWidth，即是最大正方形面积。

代码

class Solution {
    public int maximalSquare(char[][] matrix) {
        int rows = matrix.length, cols = rows > 0 ? matrix[0].length : 0;
        int maxWidth = 0;
        int[][] dp = new int[rows + 1][cols + 1];
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                if (matrix[i-1][j-1] == '1'){
                    int min = Math.min(dp[i][j - 1], dp[i - 1][j]);
                    dp[i][j] = Math.min(min, dp[i - 1][j - 1]) + 1;
                    maxWidth = dp[i][j] > maxWidth ? dp[i][j]:maxWidth;
                }
            }
        }
        return maxWidth *maxWidth;
    }
}