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:
/**
* @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;
}
}
![[Game of Purpose] Day 7](https://media.dev.to/cdn-cgi/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.amazonaws.com%2Fuploads%2Farticles%2F31bihbetl0ycvw217pyr.png)