85. Maximal Rectangle
Hard
Given a rows x cols
binary matrix filled with 0
's and 1
's, find the largest rectangle 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:
6
-
Explanation:
The maximal rectangle is shown in the above picture
.
Example 2:
-
Input:
matrix = [["0"]]
-
Output:
0
Example 3:
-
Input:
matrix = [["1"]]
-
Output:
1
Constraints:
-
rows == matrix.length
-
cols == matrix[i].length
-
1 <= row, cols <= 200
-
.matrix[i][j]
is'0'
or'1'
Solution:
class Solution {
/**
* @param String[][] $matrix
* @return Integer
*/
function maximalRectangle($matrix) {
if (!$matrix) {
return 0;
}
$result = 0;
$m = count($matrix);
$n = count($matrix[0]);
$L = array_fill(0, $n, 0);
$H = array_fill(0, $n, 0);
$R = array_fill(0, $n, $n);
for ($i = 0; $i < $m; $i++) {
$left = 0;
for ($j = 0; $j < $n; $j++) {
if ($matrix[$i][$j] == '1') {
$L[$j] = max($L[$j], $left);
$H[$j] += 1;
} else {
$L[$j] = 0;
$H[$j] = 0;
$R[$j] = $n;
$left = $j + 1;
}
}
$right = $n;
for ($j = $n - 1; $j >= 0; $j--) {
if ($matrix[$i][$j] == '1') {
$R[$j] = min($R[$j], $right);
$result = max($result, $H[$j] * ($R[$j] - $L[$j]));
} else {
$right = $j;
}
}
}
return $result;
}
}
Contact Links