Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.
Example:
Input:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
Output: 6
View every row as a base line then we just have to solve
height(matrix) times the problem of
84. Largest Rectangle in Histogram.
/**
* @param {character[][]} matrix
* @return {number}
*/
let maximalRectangle = function (matrix) {
const height = matrix.length;
if (height <= 0) {
return 0;
}
const width = matrix[0].length;
if (width <= 0) {
return 0;
}
const heights = [];
let max = 0;
for (let row = 0; row < height; row++) {
for (let col = 0; col < width; col++) {
heights[col] = ((heights[col] || 0) + 1) * matrix[row][col];
}
max = Math.max(max, largestRectangleArea(heights));
}
return max;
};
/**
* @param {number[]} heights
* @return {number}
*/
function largestRectangleArea(heights) {
const stack = [-1];
let max = 0;
for (let i2 = 0; i2 <= heights.length; i2++) {
while ((heights[i2] || 0) < heights[stack[stack.length - 1]]) {
const i = stack.pop();
const i1 = stack[stack.length - 1];
max = Math.max(max, heights[i] * (i2 - i1 - 1));
}
stack.push(i2);
}
return max;
}Same idea as above. Use DP to cache accumulated states.
Pick a pivot point (row, col) and assume it is on the base
line. The adjoining 1s above (row, col) makes up
the height of the rectangle. The width of the rectangle is determined by
how many ajoining bars are taller than the pivot bar.
So for the rectangle whose bottom pivot is (row, col):
area(row, col) to be the area.height(row, col) to be the height.left(row, col) to be the col value of
the bottom-left corner.
right(row, col) to be the col value of
the bottom-right corner.
Also:
conLeft(row, col) to be the col value
of the leftmost cell of the consecutive 1s on the left of
(row, col).
conRight(row, col) to be the col value
of the rightmost cell of the consecutive 1s on the right of
(row, col).
With conLeft and conRight we can know if the
rectangle on (row, col) shrinks comparing to
(row-1, col).
if matrix[row][col] == 1
height(row, col) = height(row-1, col) + 1
// see how long this horizontal line can get
conLeft(row, col) = conLeft(row, col-1)
conRight(row, col) = conRight(row, col+1)
// width can only be shorter
left(row, col) = max( left(row-1, col), conLeft(row, col) )
right(row, col) = min( right(row-1, col), conRight(row, col) )
if matrix[row][col] == 0
height(row, col) = 0
conLeft(row, col) = col + 1
conRight(row, col) = col - 1
left(row, col) = 0 // back to leftmost position
right(row, col) = matrix.width // back to rightmost position
area(row, col) = (right(row, col) - left(row, col) + 1) * height(row, col)We only need to keep the last state. Use dynamic arrays to reduce space complexity.
/**
* @param {character[][]} matrix
* @return {number}
*/
let maximalRectangle = function (matrix) {
const height = matrix.length;
if (height <= 0) {
return 0;
}
const width = matrix[0].length;
if (width <= 0) {
return 0;
}
const heights = new Array(width).fill(0);
const lefts = new Array(width).fill(0);
const rights = new Array(width).fill(width);
let max = 0;
for (let row = 0; row < height; row++) {
let conLeft = 0;
let conRight = width - 1;
for (let col = 0; col < width; col++) {
if (matrix[row][col] === "1") {
heights[col] = heights[col] + 1;
lefts[col] = Math.max(lefts[col], conLeft);
} else {
heights[col] = 0;
lefts[col] = 0;
conLeft = col + 1;
}
}
for (let col = width - 1; col >= 0; col--) {
if (matrix[row][col] === "1") {
rights[col] = Math.min(rights[col], conRight);
} else {
rights[col] = width;
conRight = col - 1;
}
}
for (let col = 0; col < width; col++) {
max = Math.max(max, (rights[col] - lefts[col] + 1) * heights[col]);
}
}
return max;
};☆: .｡. o(≧▽≦)o .｡.:☆☆: .｡. o(≧▽≦)o .｡.:☆☆: .｡. o(≧▽≦)o .｡.:☆
☆: .｡. o(≧▽≦)o .｡.:☆☆: .｡. o(≧▽≦)o .｡.:☆