Maximal Rectangle
Maximal Square #medium
Given an m x n
binary matrix
filled with 0
‘s and 1
‘s, find the largest square containing only 1
‘s and return its area.
Example 1:
Input: matrix = [[“1”,”0”,”1”,”0”,”0”],[“1”,”0”,”1”,”1”,”1”],[“1”,”1”,”1”,”1”,”1”],[“1”,”0”,”0”,”1”,”0”]]
Output: 4
Example 2:
Input: matrix = [[“0”,”1”],[“1”,”0”]]
Output: 1
Example 3:
Input: matrix = [[“0”]]
Output: 0
Constraints:
-
m == matrix.length
-
n == matrix[i].length
-
1 <= m, n <= 300
-
matrix[i][j]
is'0'
or'1'
.
Solution
DP
直接用 DP O(mn)/O(mn)
==space can be minimized to O(n),因为每次只考虑相邻两行==
每个 dp[i,j]
都记录当前形成的最大的 square 的 area 记录在表里面,
然后我们 从左往右,从上往下 遍历
对于 dp[i,j]
,
- 如果
matrix[i,j] == 1
我们通过画图可以得到
dp[i,j] = min(dp[i-1,j], dp[i-1,j-1], dp[i,j-1]) + 1
其余的就 ignore。
1 | public class Solution { |
Comments