Appearance
85. 最大矩形
原题链接：LeetCode 85. 最大矩形
题目描述
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例 1：
**输入：**matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] **输出：**6 **解释：**最大矩形如上图所示。
示例 2：
**输入：**matrix = [["0"]] **输出：**0
示例 3：
**输入：**matrix = [["1"]] **输出：**1
提示：
- `rows == matrix.length`
- `cols == matrix[0].length`
- `1 <= rows, cols <= 200`
- `matrix[i][j]` 为 `'0'` 或 `'1'`
难度： Hard
题解代码
javascript
/**
* @param {character[][]} matrix
* @return {number}
*/
var maximalRectangle = function(matrix) {
let max = 0
let reg = /1{1,}/g
// 构建连续的1的起始位置的二维数组
let arr = matrix.map(item => {
let str = item.join('')
let r = reg.exec(str)
let res = []
while (r) {
res.push([r.index, r.index + r[0].length - 1])
r = reg.exec(str)
}
return res
})
// 递归计算相邻的矩形
let maximalRect = (arr, n = 1) => {
let top = arr.pop()
let next = arr.pop()
if (!next || (next && !next.length)) {
let maxWidth = 0
for (let i = 0, il = top.length; i < il; i++) {
if (top[i][1] - top[i][0] + 1 > maxWidth) {
maxWidth = top[i][1] - top[i][0] + 1
max = Math.max(max, maxWidth * n)
}
}
return
}
let tt, nn, start, end, width = 1, newArr = [];
n++
for (let i = 0, il = top.length; i < il; i++) {
tt = top[i]
for (let j = 0, jl = next.length; j < jl; j++) {
nn = next[j]
width = Math.min(tt[1], nn[1]) - Math.max(tt[0], nn[0]) + 1
if (width >= 1) {
start = Math.max(tt[0], nn[0])
end = Math.min(tt[1], nn[1])
newArr.push([start, end])
max = Math.max(max, n * width)
}
}
if (tt[1] - tt[0] + 1 > width) {
max = Math.max(max, tt[1] - tt[0] + 1)
}
}
arr.push(newArr)
maximalRect(arr, n++)
}
// 横向
while (arr.length) {
maximalRect([].concat(arr))
arr.pop()
}
return max >= 0 ? max : -1
};