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
Top comments (0)