221. 最大正方形

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

示例:

输入:

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

输出: 4

思路：动态规划

思路参考：https://leetcode-cn.com/problems/maximal-square/solution/li-jie-san-zhe-qu-zui-xiao-1-by-lzhlyle/
dp[i][j]表示以(i,j)坐标为右下角的最大正方形的边长 转态转移方程为：dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1; 假设三者的正方形的边长最小值为k，则

• dp[i-1][j-1]表示以(i-1,j-1)坐标为右下角的最大正方形的边长,该正方形的上下区间和左右区间为(i-2-k, i-1) 和 (j-2-k, j-1)
• dp[i-1][j]表示以(i-1,j)坐标为右下角的最大正方形的边长,该正方形的上下区间和左右区间为(i-2-k, i-1) 和 (j-1-k, j)
• dp[i][j-1]表示以(i,j-1)坐标为右下角的最大正方形的边长,该正方形的上下区间和左右区间为(i-1-k, i) 和 (j-2-k, j-1)

把图画出来，可以看出如果刚好(i, j)坐标为1, 则可以形成一个变成为k+1的正方形 初识值为第一行和第一列的matrix[][]为1的单位dp[i][j]为1

 1 class Solution {
 2     public int maximalSquare(char[][] matrix) {
 3 
 4         if(matrix.length == 0 || matrix[0].length == 0){
 5             return 0;
 6         }
 7         int rows = matrix.length;
 8         int cols = matrix[0].length;
 9         int[][] dp = new int[rows][cols];
10 
11         int maxLenSide = 0;
12         for(int i = 0; i < rows; i++){
13             for(int j = 0; j < cols; j++){
14                 if(matrix[i][j] == '1'){
15                     if(i == 0 || j == 0){
16                         dp[i][j] = 1;       // 第一行和第一列的'1'的dp[i][j]都为1
17                     }else{
18                         dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1;
19                     }
20                     maxLenSide = Math.max(maxLenSide, dp[i][j]);
21                 }
22             }
23         }
24         return maxLenSide * maxLenSide;
25     }
26 }

leetcode 执行用时：6 ms > 83.67%, 内存消耗：41.7 MB > 84.07%

复杂度分析：

时间复杂度：O(n*m)。遍历了整个matrix[][], 所以时间复杂度为O(n*m)。 空间复杂度：O(n*m)。因为需要一个与matrix[][]等大小的二维数组，所以空间复杂度也为O(n*m)。