矩阵 - Githubissues

解题:(堆栈)

function rec(arr) {
  let result = []
  let reg = /1{2,}/g

  arr = arr.map(m => {
    let str = m.join('')
    let r = reg.exec(str)
    let re = []
    while(r) {
      re.push([r.index, r.index + r[0].length-1])
      r = reg.exec(str)
    }
    return re
  })
  // 出栈(后进先出)
  while(arr.length > 1) {
    maxRec([].concat(arr), result)
    // 这里将原数组继续出栈,从而使当前项为第一项,达到换行的目的
    arr.pop()
  }

  let max = 0
  let item = result.pop()
  while(item) {
    if (item > max) {
      max = item
    }
    item = result.pop()
  }

  function maxRec(arr, result, n = 1) {
    // 弹出相邻两项,进行排列,取交集
    let top = arr.pop()
    let next = arr.pop()

    let tt
    let nn

    let start
    let end

    let width = 1
    let maxWidth = 1

    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])
        if (width > maxWidth) {
          maxWidth = width
          start = Math.max(tt[0], nn[0])
          end = Math.min(tt[1], nn[1])
        }
      }
    }

    if (start === undefined || end === undefined) {
      // 前两行都没有交集的话
      if (n < 3) {
        return
      } else {
        width = top[0][1] - top[0][0] + 1
        if (width > 1) {
          result.push((n-1) * width)
        }
      }
    } else {
      // 继续进栈,与下一项比较 是否有交集
      arr.push([[start, end]])
      maxRec(arr, result,n++)
    }
  }

  return max > 0 ? max : -1
}

lynhao / day-by-day

矩阵 #12

题目: 给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。