Difficulty | Related Topics | Similar Questions | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Hard |
|
|
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}
*/
var 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 1
s 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)
:
- Define
area(row, col)
to be the area. - Define
height(row, col)
to be the height. - Define
left(row, col)
to be thecol
value of the bottom-left corner. - Define
right(row, col)
to be thecol
value of the bottom-right corner.
Also:
- Define
conLeft(row, col)
to be thecol
value of the leftmost cell of the consecutive1
s on the left of(row, col)
. - Define
conRight(row, col)
to be thecol
value of the rightmost cell of the consecutive1
s 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}
*/
var 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
};
Template generated via Leetmark.