leetcode hot 100- 221. 最大正方形

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的正方形 leetcode hot 100- 221. 最大正方形 初识值为第一行和第一列的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)。
上一篇:MySQL常用查询方法


下一篇:干货|咦?还可以这样图解Word2Vec