Skip to main content

85. Maximal Rectangle

分析

基于 84. Largest Rectangle in Histogram 建立个 allLevelsHeights ,然后每一层用 84 的解法求一波 Pasted image 20220502205206.png

题解

function maximalRectangle(matrix: string[][]): number {
let ans = 0
// 求出每一层的heights
const allLevelsHeights: number[][] = []
for (let i = 0; i < matrix.length; i++) {
allLevelsHeights[i] = []
for (let j = 0; j < matrix[0].length; j++) {
if (i === 0) {
if (matrix[0][j] === "1") {
allLevelsHeights[0][j] = 1
} else {
allLevelsHeights[0][j] = 0
}
continue
}
if (matrix[i][j] === "1") {
allLevelsHeights[i][j] = allLevelsHeights[i - 1][j] + 1
} else {
allLevelsHeights[i][j] = 0 // 注意这里
}
}
ans = Math.max(ans, largestRectangleArea(allLevelsHeights[i]))
}
return ans
}

function largestRectangleArea(heights: number[]): number {
let ans = 0
const leftFirstSmallerIndex = [],
rightFirstSmallerIndex = []
const monoStack = []
for (let i = 0; i < heights.length; i++) {
const currentHeight = heights[i]
while (monoStack.length && heights[monoStack[monoStack.length - 1]] >= currentHeight) {
monoStack.pop()
}
leftFirstSmallerIndex[i] = monoStack.length ? monoStack[monoStack.length - 1] : -1
monoStack.push(i)
}
monoStack.length = 0
for (let i = heights.length - 1; i >= 0; i--) {
const currentHeight = heights[i]
while (monoStack.length && heights[monoStack[monoStack.length - 1]] >= currentHeight) {
monoStack.pop()
}
rightFirstSmallerIndex[i] = monoStack.length ? monoStack[monoStack.length - 1] : heights.length
monoStack.push(i)
}
for (let i = 0; i < heights.length; i++) {
ans = Math.max(ans, (rightFirstSmallerIndex[i] - leftFirstSmallerIndex[i] - 1) * heights[i])
}
return ans
}