221. Maximal Square

发表于 | 分类于 | 浏览 次

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:

1
2
3
4
5
6
7
8
Input: 

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

Output: 4

解法1

首先为原矩阵生成一个同样大小的新矩阵dp
dp[i][j]表示以index[i][j]作为右下角的正方形的最大边长.
dp[i][j] = min{dp[i][j-1], dp[i-1][j-1], dp[i-1][j-1]}.
为什么一定要考虑dp[i-1][j-1]呢?下面举个例子说明
例如当前dp矩阵为

1
2
[[0,1],
 [1,1]]

则以位置[1,1]为右下角的最大的正方形的边长为1,因为,位置[0,0]处的边长为0, 即位置[0,0]上的元素为0.