这道题很难想,主要有两种解法,一种是把这道题目转化成之前那道(#084)直方图面积计算的题目,使用栈来做,但是还有更优雅的方法,使用DP。这两种方法的时间复杂度都是O(mn),空间复杂度都是O(n)。

题目

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.

For example, given the following matrix:

1 0 1 0 0

1 0 1 1 1

1 1 1 1 1

1 0 0 1 0

Return 6.

解法一:直方图面积

参考链接

行遍历,沿着这一行将矩阵切开,行上面的矩阵看做#84题目中的直方图,计算上面直方图面积的最大值。在遍历所有行之后,得到的面积最大值就是最大面积。

解法二:DP

参考链接

行遍历,沿着一行进行扫描,我们对于矩阵中的每个位置需要维护三个量:H 高度, L 左边界, R 右边界,这三个量将被用来计算一个矩形面积

0 0 0 1 0 0 0

0 0 1 1 1 0 0

0 1 1 1 1 1 0

我们来考虑上面的矩阵

在遍历第一行时,

高度H:0001000

遍历第二行时,只需要考虑前一行已存储的状态和这一行的值就可以了,直接在H的基础上修改就可以了

高度H:0012100

对于左右边界,情况复杂一点,需要考虑前一行存储的状态和这一行已扫面过的状态

遍历第一行时,

左边界L:0003000

遍历第二行时,

左边界L:0023200

在下面的代码中,使用curleft存储的值表示当前块的最左边,在最终决定左边界时,要考虑到上一行如果已经有已存在的左边界时,就选取上一行左边界值作为当前左边界(如第二行L的232中的3)。

这样每一行遍历时,内部就可以表示不同起始边界的矩形块了。

右边界同理。

该动态规划的过程就是利用了上一行的信息。

DP代码

一个容易理解的版本,后面还有一个做了代码优化的版本

做了一些代码优化,6ms,轻松超过90%

 

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注