leetcode 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.
For example, given the following matrix:
1 | 1 0 1 0 0 |
Return 4.
1 | class Solution { |
- dp[i][j] = min(dp[i-1][j-1], dp[j-1][i], dp[i][j-1]) + 1 if(matrix[i-1][j-1] == 1)
- 这里dp记录的是边长,只有当前点的左边,上边和左上角一般大时,当前点的值才加一
1 (dp = 1) | 1 (dp = 1) | 0 (dp = 0) |
---|---|---|
0 (dp = 0) | 1 (dp = 1) | 1 (dp = 1) |
0 (dp = 0) | 1 (dp = 1) | 1 (dp = 2) |
- 要注意的是,如果最后一个位置的值为0的话,dp = 0 ,因此需要一个变量来保存整个过程中的最大值