问问题，0/1 矩阵内最大1矩阵的问题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问问题，0/1 矩阵内最大1矩阵的问题

问问题，0/1 矩阵内最大1矩阵的问题# JobHunting - 待字闺中

x*g2011-04-05 07:04

1 楼

0/1 矩阵内最大1矩阵的问题
看了版上的讨论，建议直方图内切矩阵来解决
按照行/列加分别得到一个直方图
然后求最大的内切矩阵
得到左右的range，四个range就是最大1矩阵
这个思路正确吗？
如果是对的，很容易就找到反例了，比如
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
1 0 1 0 1
行列相加得到的一维向量都是3,2,3,2,3
直方图就是这个样子的
| | |
| | | | |
| | | | |
最大的内切举证都是从0-4，面积是2x5 =10
谁能指点一下么？

d*l2011-04-05 07:04

2 楼

其实是对于每行，只累加从这一行开始向上连续的1，你的例子应该是
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
1 0 1 0 1

x*g2011-04-05 07:04

3 楼

明白了，是我想错了，多谢。:)

【在 d*******l 的大作中提到】

: 其实是对于每行，只累加从这一行开始向上连续的1，你的例子应该是
: 0 1 0 1 0
: 1 0 1 0 1
: 0 1 0 1 0
: 1 0 1 0 1
: 1 0 1 0 1

x*g2011-04-05 07:04

4 楼

继续问
那个被1包围的0的最大矩阵的题目
也是用同样的方法，统计连续向上0的个数，对么？

d*l2011-04-05 07:04

5 楼

额，这个题到没听说过，上面的方法好像不太适用。“包围”是指那个全0矩阵周围一
圈严格的被1包围？这个条件不太方便简单的判断，我能想到O(n^3)还是能做出来的，
你确定这个有平方复杂度的做法吗？

【在 x******g 的大作中提到】

: 继续问
: 那个被1包围的0的最大矩阵的题目
: 也是用同样的方法，统计连续向上0的个数，对么？

x*g2011-04-05 07:04

6 楼

不能诶，不过我想了一下能不能这么解
0 1 0 1 0
0 1 1 1 1
1 1 0 0 1
0 1 0 0 1
1 1 0 0 1
1 1 1 1 1
-》每行统计连续上升的0，跟你刚才说的方法一样的话得到
1 0 1 0 1
2 0 0 0 0
0 0 1 1 0
1 0 2 2 0
0 0 3 3 0
0 0 0 0 0
如果是被1包围的，那它周围必定都是0，而且是个矩形
就变成直方图里面找个矩形，而且两侧都是0，比前面那个应该还简单一些
这么解可以么？

d*l2011-04-05 07:04

7 楼

又想了想，上面的做法大概还是可以的，和你说的差不多。任何一个被1包围的0矩阵肯
定是局部最大的0矩阵，也就是说在上面那种做法中，在对每一行运用直方图方法的时
候，会被作为一个局部的最大值去更新整体的最大值。这个问题中，我想只要判断一下
，只对那些被1包围的0矩阵，才去更新整体最大值，就能得到结果。
不过你没说一个很关键的地方就是怎么在常数时间判断一个0矩阵是否被1包围，你说只
是检查两侧我觉得还是不够的，你这样存在的固然能找出来，却有可能将实际不是的给
误算上。比如你的例子如果改成这样：
1 0 1 0 1
2 0 0 0 0
0 0 1 1 0
1 0 2 2 0
0 0 3 3 0
0 0 1 0 0
那你的方法可能就会把那部分算上，其实并不应该算。
不过这个方法应该还是能行的通的，可以利用0-1矩阵的特点。先预处理得到矩阵每个
点与左上角确定的矩形的面积a[i][j]，所谓面积就是所有值的累加。这个是n^2时间内
能完成的。然后通过一些简单的加减就能在常数时间内得到任何一个子矩阵的面积。假
如我们现在有一个全0矩阵，知道它右下角和左上角的位置，只需要判断比它大一圈的
那个矩阵面积是否合适就行了，因为如果内部全零，外圈全1的话，面积是唯一确定的

【在 x******g 的大作中提到】

: 不能诶，不过我想了一下能不能这么解
: 0 1 0 1 0
: 0 1 1 1 1
: 1 1 0 0 1
: 0 1 0 0 1
: 1 1 0 0 1
: 1 1 1 1 1
: -》每行统计连续上升的0，跟你刚才说的方法一样的话得到
: 1 0 1 0 1
: 2 0 0 0 0

g*e2011-04-05 07:04

8 楼

这题跟矩阵内找max subarray sum是相同的方法。唯一的区别是你这题是找直方图最大
面积
，max sum是找array内连续subarray最大和，都是O(n)，最后的复杂度都是O(n^3)

【在 x******g 的大作中提到】

: 0/1 矩阵内最大1矩阵的问题
: 看了版上的讨论，建议直方图内切矩阵来解决
: 按照行/列加分别得到一个直方图
: 然后求最大的内切矩阵
: 得到左右的range，四个range就是最大1矩阵
: 这个思路正确吗？
: 如果是对的，很容易就找到反例了，比如
: 0 1 0 1 0
: 1 0 1 0 1
: 0 1 0 1 0

x*g2011-04-05 07:04

9 楼

你说的对，光检查两侧不能确定是包围的
求和的方法包围矩阵的和是确定值
但是确定值不能肯定是个包围矩阵，也需要再考虑一下

【在 d*******l 的大作中提到】

: 又想了想，上面的做法大概还是可以的，和你说的差不多。任何一个被1包围的0矩阵肯
: 定是局部最大的0矩阵，也就是说在上面那种做法中，在对每一行运用直方图方法的时
: 候，会被作为一个局部的最大值去更新整体的最大值。这个问题中，我想只要判断一下
: ，只对那些被1包围的0矩阵，才去更新整体最大值，就能得到结果。
: 不过你没说一个很关键的地方就是怎么在常数时间判断一个0矩阵是否被1包围，你说只
: 是检查两侧我觉得还是不够的，你这样存在的固然能找出来，却有可能将实际不是的给
: 误算上。比如你的例子如果改成这样：
: 1 0 1 0 1
: 2 0 0 0 0
: 0 0 1 1 0

x*g2011-04-05 07:04

10 楼

啊，难道我又弄错了？
直方图内切矩形的算法不是O(n)的吗？
那最后的复杂度不该是O(n^2)吗？

【在 g**e 的大作中提到】

: 这题跟矩阵内找max subarray sum是相同的方法。唯一的区别是你这题是找直方图最大
: 面积
: ，max sum是找array内连续subarray最大和，都是O(n)，最后的复杂度都是O(n^3)

g*e2011-04-05 07:04

11 楼

任意n行里任意选两行，一共有n(n-1)/2种选择，每个都需要O(n)求最大值方图，总共O
(n^3)

最大

【在 x******g 的大作中提到】

: 啊，难道我又弄错了？
: 直方图内切矩形的算法不是O(n)的吗？
: 那最后的复杂度不该是O(n^2)吗？