最大矩形

exec的使用文檔

export default (arr) => {
  let result = []
  let reg = /1{2,}/g
  // 把二維數組重新表達，把相鄰的1提取出來
  arr = arr.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
  })
  // 通過遞歸計算相鄰矩陣
  let maxRect = (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.max(tt[1], nn[1])
        }
      }
    }
    // 沒有交叉點
    if (start === undefined || end === undefined) {
      if (n < 3) {
        return false
      } else {
        width = top[0][1] - top[0][0] + 1
        if (width > 1) {
          result.push((n - 1) * width)
        }
      }
    } else {
      arr.push([[start, end]])
      maxRect(arr, result, n++)
    }
  }
  while (arr.length > 1) {
    // 要值拷貝，因數組在javascript中時引用類型
    maxRect([].concat(arr), result)
    arr.pop()
  }
  let max = 0
  let item = result.pop()
  while (item) {
    if (item > max) {
      max = item
    }
    item = result.pop()
  }
  return max > 0 ? max : -1
}