wengzc
commented
3 years ago 思路分析：化抽象为已解决的问题，转化为LeetCode 84. 柱状图中最大的矩形求解
/**
* @param {character[][]} matrix
* @return {number}
*/
var maximalRectangle = function (matrix) {
let len = matrix.length
if (!len) return 0
let heights = new Array(matrix[0].length).fill(0)
let max = 0
for (let i = 0; i < len; i++) {
// 遍历每行的高度,用LeetCode 84题方法(栈)求出最大矩形
for (let j = 0; j < matrix[i].length; j++) {
if (matrix[i][j] === '1') {
heights[j]++
} else {
heights[j] = 0
}
}
max = Math.max(max, largestRectangleArea(heights))
}
return max
// LeetCode 84. 柱状图中最大的矩形
function largestRectangleArea(heights) {
// 在heights后面加一个0，处理heights全为递增数组时，强迫栈内元素出栈
heights.push(0)
let len = heights.length
let stack = []
let max = 0
for (let i = 0; i < len; i++) {
while (stack.length && heights[stack[stack.length - 1]] >= heights[i]) {
let top = stack.pop()
let height = heights[top]
// 求以 height 为当前高度的矩形的最最大面积
if (!stack.length) {
max = Math.max(max, i * height)
} else {
let left = stack[stack.length - 1]
let right = i
max = Math.max(max, (right - left - 1) * height)
}
}
stack.push(i)
}
return max
};
};
给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例:
题目链接：https://leetcode-cn.com/problems/maximal-rectangle