题目

英文

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

Example:

Input:

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

Output: 4

中文

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

思路

  • 动态规划(主要用户将一个复杂的问题分解为多个建单的问题，求最优解时)。
  • 声明一个空间和原有二位数据大小一样的二位数组(tmp[i][j])。
  • 计算每一个节点最大正方形的边长，并存储与该节点（利用之前节点计算当前节点最大正方形边长）。
  • 取tmp[i][j]得最大值的平凡返回。

    代码

第一版代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
  function maximalSquare($matrix) {
      $hight =  count($matrix);
      if($hight<1)
      {
          return 0;
      }
      $wide = 0;
      if($hight > 0){
          $wide= count($matrix[0]);
      }
      $ret = 0;
      for($i = 1; $i<= $hight; $i++)
      {
          $tmp = $this->getRet($matrix, $i, $hight, $wide);
          if($ret <$tmp ){
              $ret = $tmp;
          }
      }
      return $ret;
  }
    
  public function getRet($matrix, $i, $hight, $wide)
  {
    //起始点纵向坐标  
    for($h = 0; $h<= $hight-$i; $h++ )
    {   
        for($j = 0;$j <= $wide-$i; $j++)
        {
            //h 为起点高，j为起点宽。
            $ret = 1;
            for($m = $h; $m <$h + $i; $m++){
                for($k = $j; $k < $j + $i; $k++){
                    if($matrix[$m][$k] == 0)
                    {
                        $ret = 0;
                        break;
                    }
                }
                if($ret == 0) {
                    break;
                }
            }
            if($ret == 1){
                return $i*$i;
            }
        }
    }
    return 0;
  }
    
}

用php跑测试用例，跑了2.5秒。😓

回头用c重写下试试。

1
待定

最优解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int maximalSquare(char[][] matrix) {
        /**
        dp[i][j]表示以第i行第j列为右下角所能构成的最大正方形边长, 则递推式为: 
        dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]);
        **/
        int m = matrix.length;
        if(m < 1) return 0;
        int n = matrix[0].length;
        int max = 0;
        int[][] dp = new int[m+1][n+1];
        
        for(int i = 1; i <= m; ++i) {
            for(int j = 1; j <= n; ++j) {
                if(matrix[i-1][j-1] == '1') {
                    dp[i][j] = 1 + Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1]));
                    max = Math.max(max, dp[i][j]); 
                }
            }
        }
        
        return max*max;
    }
}