关于leetcode的测试用例
来源:7-5 最大矩阵-代码实操(2)

Nick_arron
2019-07-31
应该是leetcode更新了很多测试用例,导致目前无法通过了。
对于问题的理解:目前对于只有一个1或者一行1或者一列1,leetcode都认为是矩形,根据老师的代码改了一些边界条件,暂时可以通过所有用例,但是性能很差。
提供如下,欢迎指正。
function maximalRectangle (matrix) {
if (!matrix.length) return 0
let result = []
let reg = /1+/g
matrix = matrix.map(item => {
let str = item.join('')
let r = reg.exec(str)
let rs = []
while (r) {
rs.push([r.index, r.index + r[0].length - 1])
r = reg.exec(str)
}
return rs
})
if (matrix.length < 2) {
matrix[0].map(posArr => {
result.push(posArr[1] - posArr[0] + 1)
})
}
let calc = (arr, n = 1) => {
let top = arr.pop()
let next = arr.pop()
let tt
let nn
let start
let end
let width = 1
let minWidth = 0
let temp = []
let max = result.length > 0 ? Math.max(...result) : 0
n++
for (let i = 0, lt = top.length; i < lt; i++) {
tt = top[i]
if (tt && tt[1] - tt[0] + 1 > max) {
result.push(tt[1] - tt[0] + 1)
}
for (let j = 0, ln = next.length; j < ln; j++) {
nn = next[j]
if (nn && nn[1] - nn[0] + 1 > max) {
result.push(nn[1] - nn[0] + 1)
}
width = Math.min(tt[1], nn[1]) - Math.max(tt[0], nn[0])
if (width >= minWidth) {
start = Math.max(tt[0], nn[0])
end = Math.min(tt[1], nn[1])
temp.push([start, end])
}
}
}
if (start === undefined || end === undefined) {
if (n < 3) {
return false
} else {
width = top[0][1] - top[0][0] + 1
if (width > 1) {
result.push(width * (n - 1))
}
}
} else {
if (arr.length > 0) {
// 这里应该是有问题的
let maxWidth = 0
temp.map((posArr) => {
if (posArr[1] - posArr[0] > maxWidth) {
maxWidth = posArr[1] - posArr[0]
}
})
result.push(n * (maxWidth + 1))
arr.push(temp)
calc(arr, n++)
} else {
// 到最后一行
let maxWidth = 0
temp.map((posArr) => {
if (posArr[1] - posArr[0] > maxWidth) {
maxWidth = posArr[1] - posArr[0]
}
})
result.push(n * (maxWidth + 1))
}
}
}
while (matrix.length > 1) {
calc([].concat(matrix))
matrix.pop()
}
return result.length > 0 ? Math.max(...result) : 0
}
写回答
1回答
-
快乐动起来呀
2019-08-01
嗯,leetcode的测试用例在不断更新,目前这道题的算法确实不是最优解,等我更新的,也欢迎把你的算法贡献到 git.imooc.com 的 issue 区哈,分享更多同学学习
00
相似问题