var maximalRectangle = function (matrix) {
let max = 0
if (matrix.length === 0) {
return 0
}
let heights = new Array(matrix[0].length)
for (let r = 0; r < matrix.length; r++) {
let row = matrix[r]
for (let c = 0; c < row.length; c++) {
let item = row[c]
if (item === '1') {
if (heights[c]) {
heights[c]++
} else {
heights[c] = 1
}
} else {
heights[c] = 0
}
}
max = Math.max(largestRectangleArea(heights), max)
}
return max
};
var largestRectangleArea = function (heights) {
const stack = []
let max = 0
let i = 0
while (i < heights.length) {
if (stack.length === 0) {
stack.push(i)
i++
} else {
let topIndex = stack[stack.length - 1]
let cur = heights[i]
// 如果当前元素高 大于等于 栈顶元素的高; 直接入栈, 否则需要计算面积
if (cur >= heights[topIndex]) {
stack.push(i)
i++
} else {
// 拿到栈顶元素, 同时将栈顶的元素 pop 出栈
let topH = heights[stack.pop()]
// 查看新栈顶下标的
let newTop = stack.length === 0 ? -1 : stack[stack.length - 1]
// 当前的 下标 i
let area = (i - newTop - 1) * topH
max = Math.max(max, area)
}
}
}
while (stack.length !== 0) {
let topH = heights[stack.pop()]
let newTop = stack.length === 0 ? -1 : stack[stack.length - 1]
let w = heights.length
let area = (w - (newTop + 1)) * topH
max = Math.max(max, area)
}
return max
};
const r = maximalRectangle([
["1", "0", "1", "0", "0"],
["1", "0", "1", "1", "1"],
["1", "1", "1", "1", "1"],
["1", "0", "0", "1", "0"]
])
console.log(r)
最大矩形: (85号)
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 题目链接 tag: Hard; question: Given a 2D binary matrix fille...
