x******g
发帖数: 41 | 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*******l
发帖数: 338 | 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******g
发帖数: 41 | 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******g
发帖数: 41 | 4 继续问
那个被1包围的0的最大矩阵的题目
也是用同样的方法，统计连续向上0的个数，对么？ |
d*******l
发帖数: 338 | 5 额，这个题到没听说过，上面的方法好像不太适用。“包围”是指那个全0矩阵周围一
圈严格的被1包围？这个条件不太方便简单的判断，我能想到O(n^3)还是能做出来的，
你确定这个有平方复杂度的做法吗？
【在 x******g 的大作中提到】
: 继续问
: 那个被1包围的0的最大矩阵的题目
: 也是用同样的方法，统计连续向上0的个数，对么？
|
x******g
发帖数: 41 | 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*******l
发帖数: 338 | 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**e
发帖数: 6127 | 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******g
发帖数: 41 | 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******g
发帖数: 41 | 10 啊，难道我又弄错了？
直方图内切矩形的算法不是O(n)的吗？
那最后的复杂度不该是O(n^2)吗？
【在 g**e 的大作中提到】
: 这题跟矩阵内找max subarray sum是相同的方法。唯一的区别是你这题是找直方图最大
: 面积
: ，max sum是找array内连续subarray最大和，都是O(n)，最后的复杂度都是O(n^3)
|
|
|
g**e
发帖数: 6127 | 11 任意n行里任意选两行，一共有n(n-1)/2种选择，每个都需要O(n)求最大值方图，总共O
(n^3)
最大
【在 x******g 的大作中提到】
: 啊，难道我又弄错了？
: 直方图内切矩形的算法不是O(n)的吗？
: 那最后的复杂度不该是O(n^2)吗？
|
g*********s
发帖数: 1782 | 12 几位都很牛。我已经看晕了。
共O
【在 g**e 的大作中提到】
: 任意n行里任意选两行，一共有n(n-1)/2种选择，每个都需要O(n)求最大值方图，总共O
: (n^3)
:
: 最大
|
d*******l
发帖数: 338 | 13 你这个是求最大子矩阵的方法，这样确实没错，但0-1矩阵的最大全1矩阵确实是O(n^2)
的，对每一行用一次直方图方法即可，而每行的值可以在一次O(n^2)的预处理中全部得到
共O
【在 g**e 的大作中提到】
: 任意n行里任意选两行，一共有n(n-1)/2种选择，每个都需要O(n)求最大值方图，总共O
: (n^3)
:
: 最大
|
d*******l
发帖数: 338 | 14 可以的，我们只对那些已经确定是全0的矩阵才会去检查外圈不是吗？如果知道了内部
全0这个条件，然后再得到和，就可以确定是否被包围了
【在 x******g 的大作中提到】
: 你说的对，光检查两侧不能确定是包围的
: 求和的方法包围矩阵的和是确定值
: 但是确定值不能肯定是个包围矩阵，也需要再考虑一下
|
p*****u
发帖数: 310 | 15 能不能详细点？
2)
得到
【在 d*******l 的大作中提到】
: 你这个是求最大子矩阵的方法，这样确实没错，但0-1矩阵的最大全1矩阵确实是O(n^2)
: 的，对每一行用一次直方图方法即可，而每行的值可以在一次O(n^2)的预处理中全部得到
:
: 共O
|
p*****u
发帖数: 310 | |
d*******d
发帖数: 2050 | 17 他这个直方图内接算法是n方,overall是n^3
【在 p*****u 的大作中提到】
: fond o(n^2) solution. http://blog.sina.com.cn/s/blog_411fed0c0100bw8m.html
|
t**r
发帖数: 3428 | 18 没看懂，谁给给个详细的链接或者解释？谢了
什么叫 ’求直方图的内切矩阵” |
s*****n
发帖数: 5488 | 19 最简单的算法，用大家喜爱的DP. 非常非常简单o(n^2)。
【在 x******g 的大作中提到】
: 0/1 矩阵内最大1矩阵的问题
: 看了版上的讨论，建议直方图内切矩阵来解决
: 按照行/列加分别得到一个直方图
: 然后求最大的内切矩阵
: 得到左右的range，四个range就是最大1矩阵
: 这个思路正确吗？
: 如果是对的，很容易就找到反例了，比如
: 0 1 0 1 0
: 1 0 1 0 1
: 0 1 0 1 0
|
k*j
发帖数: 153 | 20 发现了这个webpage有很好的解释。有好几种做法，包括怎么将这题转换到经典问题来
做。推荐给大家看看。
http://blog.csdn.net/linulysses/article/details/5594141 |
