最大矩阵-代码有问题

Question

虽然说堆栈讲的不错，但是最大矩阵的解题思路略有瑕疵。

迷糊了好一阵，讲的和自己想的一直不能吻合，好烦躁。。。

js不太熟，捋了2个多小时，才搞清楚。

略做分享说明，供交流，参考。

示例代码，一直拿最宽的是不对的，这个思路有问题，即使每一行都重新算也是不行，当有特别窄的，但有细长的矩阵（实际面积大），与宽的，特别短的矩阵（实际面积小）共存，并且都参与第一遍历的时候，窄的矩阵会被漏掉。

这个题，应该是更复杂的，需要做所有矩阵面积的记录，取最大值。

如果说的不对，请指教，虚心学习，先谢谢。

测试数据：

test('rectangle5', () => {
    let input = [
        ['1', '1', '0', '0', '0', '0'],
        ['1', '1', '0', '1', '1', '0'],
        ['1', '1', '0', '1', '1', '1'],
        ['1', '1', '0', '1', '1', '1'],
        ['1', '1', '0', '1', '1', '1']
    ]
    expect(rectangle(input)).toBe(10)
})

测试结果：

 FAIL  test/stack/lesson2.test.js
  ✕ rectangle5 (17ms)

  ● rectangle5

    expect(received).toBe(expected) // Object.is equality

    Expected: 10
    Received: 8

      50 |         ['1', '1', '0', '1', '1', '1']
      51 |     ]
    > 52 |     expect(rectangle(input)).toBe(10)
         |                              ^
      53 | })
      54 | 
      55 | // test('rectangle6', () => {

      at Object.toBe (test/stack/lesson2.test.js:52:30)

  console.log code/stack/lesson2.js:16
    [
      [ [ 0, 1 ] ],
      [ [ 0, 1 ], [ 3, 4 ] ],
      [ [ 0, 1 ], [ 3, 5 ] ],
      [ [ 0, 1 ], [ 3, 5 ] ],
      [ [ 0, 1 ], [ 3, 5 ] ]
    ]

Test Suites: 1 failed, 1 total
Tests:       1 failed, 1 total
Snapshots:   0 total
Time:        1.337s, estimated 2s

用stark+位计算进行修改bug
最大矩阵.js

// 用stark+位计算
/**
 * @param {any[]} arr
 */
export default arr => {
    let areas = []
    let reg = /1{2,}/g
    /**
     * @param {string} str
     */
    let getWidth = str => {
        let r = reg.exec(str)
        let rs = []
        while (r) {
            rs.push(r[0].length)
            r = reg.exec(str)
        }
        return rs
    }
    /**
     * @param {any} _pres
     * @param {any[]} _cur
     * @param {number} _curIndex
     */
    let loop = (_pres, _cur, _curIndex) => {
        if (_pres.length === 0) {
            return
        } else {
            let intersection = (
                parseInt(_pres.pop().join(''), 2) & parseInt(_cur.join(''), 2)
            ).toString(2)
            getWidth(intersection).map(item =>
                // 计算面积
                areas.push(item * (_curIndex - _pres.length + 1))
            )
            // 每一行都向前单方向排列计算
            loop(_pres, intersection.split(''), _curIndex)
        }
    }
    /**
     * @param {any[]} pre
     * @param {any[]} cur
     * @param {number} index
     */
    arr.reduce((pre, cur, index) => {
        loop(
            arr.filter((_, idx) => idx < index),
            cur,
            index
        )
        return cur
    })
    return areas.length > 0 ? areas.sort((a, b) => b - a)[0] : 0
}

最大矩阵.test.js

import rectangle from '../../optimize-leetcode/stark/最大矩阵'

test('rectangle', () => {
    let input = [
        ['1', '0', '1', '0', '0'],
        ['1', '0', '1', '1', '1'],
        ['1', '1', '1', '1', '1'],
        ['1', '0', '0', '1', '0']
    ]
    expect(rectangle(input)).toBe(6)
})
test('rectangle2', () => {
    let input = [
        ['1', '0', '1', '0', '0', '1'],
        ['1', '1', '1', '1', '1', '1'],
        ['1', '1', '0', '1', '1', '1'],
        ['1', '0', '1', '0', '1', '0'],
        ['1', '0', '1', '1', '1', '1']
    ]
    expect(rectangle(input)).toBe(6)
})
test('rectangle3', () => {
    let input = [
        ['1', '1', '1', '0', '0', '0'],
        ['1', '1', '1', '0', '0', '0'],
        ['1', '1', '1', '1', '1', '1'],
        ['1', '1', '1', '1', '1', '1'],
        ['1', '1', '1', '0', '0', '0']
    ]
    expect(rectangle(input)).toBe(15)
})

test('rectangle4', () => {
    let input = [
        ['1', '1', '0', '0', '0', '0'],
        ['1', '1', '0', '0', '0', '0'],
        ['1', '1', '0', '1', '1', '1'],
        ['1', '1', '0', '1', '1', '1'],
        ['1', '1', '0', '0', '0', '0']
    ]
    expect(rectangle(input)).toBe(10)
})

test('rectangle5', () => {
    let input = [
        ['1', '1', '0', '0', '0', '0'],
        ['1', '1', '0', '1', '1', '0'],
        ['1', '1', '0', '1', '1', '1'],
        ['1', '1', '0', '1', '1', '1'],
        ['1', '1', '0', '1', '1', '1']
    ]
    expect(rectangle(input)).toBe(10)
})

test('rectangle6', () => {
    let input = [
        ['1', '1', '0', '1', '1', '1'],
        ['1', '1', '0', '1', '0', '1'],
        ['1', '1', '0', '1', '1', '1'],
        ['1', '1', '0', '1', '1', '1']
    ]
    expect(rectangle(input)).toBe(8)
})
test('rectangle7', () => {
    let input = [
        ['1', '1', '1'],
        ['1', '1', '0'],
        ['1', '1', '0']
    ]
    expect(rectangle(input)).toBe(6)
})

测试通过

 PASS  optimize-leetcode-test/stark/最大矩阵.test.js
  ✓ rectangle (2ms)
  ✓ rectangle2
  ✓ rectangle3 (1ms)
  ✓ rectangle4
  ✓ rectangle5
  ✓ rectangle6
  ✓ rectangle7 (1ms)

Test Suites: 1 passed, 1 total
Tests:       7 passed, 7 total
Snapshots:   0 total
Time:        1.39s, estimated 2s

Answer 1

快乐动起来呀 2020-01-03 21:56:21

咱们源码中有更新的代码，不过你的代码也不错，很赞

• 提问者 yeyileng #1

  老师的讲解很细致，更赞，也感谢代码官方更新。

• weixin_慕慕8136048 #2

  你好老师，我pull了最新的代码，可是发现这道题的源码依旧是取每行的最大宽度进行计算，请问老师这里需要怎么修改来避免这位同学说的问题

• aaayumi555 #3

  最新的代码还是不通过leetcode 唉