d****n 发帖数: 233 | 1 就是在一个MXN的0/1 矩阵中找边全是1的最大矩形,有没有O(MN)的解法呀? |
a********g 发帖数: 36 | 2 用动态规划.
开个m*n的额外空间.
每个cell有个row和col值
if arr[i][j] != 0
row[i][j] 和 col [i][j]
有三个候选项:
1) row[i][j] = row[i-1][j] +1; col[i][j] = 1;
2) col[i][j] = col[i][j-1]; row[i][j] = 1;
3) row[i][j] = min(row[i-1][j], row[i][j-1]) +1 ; col[i][j] = min(col[i-1][j
], col[i][j-1])+1;
取 row[i[j]]*co[i][]j最大的那一个候选项.
这个需要画个图就比较容易想清楚,说明白. |
d****n 发帖数: 233 | 3 谢了,不过没太看懂。
[j
【在 a********g 的大作中提到】 : 用动态规划. : 开个m*n的额外空间. : 每个cell有个row和col值 : if arr[i][j] != 0 : row[i][j] 和 col [i][j] : 有三个候选项: : 1) row[i][j] = row[i-1][j] +1; col[i][j] = 1; : 2) col[i][j] = col[i][j-1]; row[i][j] = 1; : 3) row[i][j] = min(row[i-1][j], row[i][j-1]) +1 ; col[i][j] = min(col[i-1][j : ], col[i][j-1])+1;
|
m**********e 发帖数: 22 | 4 需要用到一个帮助矩阵。
在每一行基于当前高度找LargestArea
然后对于每一行找到的最大面积找整个矩阵的最大面积。
参考:
http://yyeclipse.blogspot.com/2012/11/solving-maximal-rectangle
【在 d****n 的大作中提到】 : 就是在一个MXN的0/1 矩阵中找边全是1的最大矩形,有没有O(MN)的解法呀?
|
m**********e 发帖数: 22 | 5 再加一道类似的题:同样的矩阵,找最大的子方阵。这个方阵的长宽一样,每个元素都
要是1。
【在 m**********e 的大作中提到】 : 需要用到一个帮助矩阵。 : 在每一行基于当前高度找LargestArea : 然后对于每一行找到的最大面积找整个矩阵的最大面积。 : 参考: : http://yyeclipse.blogspot.com/2012/11/solving-maximal-rectangle
|
d****n 发帖数: 233 | 6 link里的跟这题不是一道题。 这是最大黑边矩形问题。
【在 m**********e 的大作中提到】 : 需要用到一个帮助矩阵。 : 在每一行基于当前高度找LargestArea : 然后对于每一行找到的最大面积找整个矩阵的最大面积。 : 参考: : http://yyeclipse.blogspot.com/2012/11/solving-maximal-rectangle
|
l*n 发帖数: 529 | 7 先处理下原矩阵,mat[i][j]=mat[i][j]==0?0:mat[i-1][j]+1
然后用histogram最大面积的o(n)算法处理每一行.
【在 d****n 的大作中提到】 : 就是在一个MXN的0/1 矩阵中找边全是1的最大矩形,有没有O(MN)的解法呀?
|
a********g 发帖数: 36 | 8 这个方法可以求最大正方形。求最大矩形,需要用直方图的方法。
[j
【在 a********g 的大作中提到】 : 用动态规划. : 开个m*n的额外空间. : 每个cell有个row和col值 : if arr[i][j] != 0 : row[i][j] 和 col [i][j] : 有三个候选项: : 1) row[i][j] = row[i-1][j] +1; col[i][j] = 1; : 2) col[i][j] = col[i][j-1]; row[i][j] = 1; : 3) row[i][j] = min(row[i-1][j], row[i][j-1]) +1 ; col[i][j] = min(col[i-1][j : ], col[i][j-1])+1;
|
s*****r 发帖数: 108 | 9 算正方形是更容易的 DP...
【在 m**********e 的大作中提到】 : 再加一道类似的题:同样的矩阵,找最大的子方阵。这个方阵的长宽一样,每个元素都 : 要是1。
|
d****n 发帖数: 233 | 10 你们讨论的都不着题呀, 这要是真面时这样就得跪了。
【在 s*****r 的大作中提到】 : 算正方形是更容易的 DP...
|
d*k 发帖数: 207 | 11 自己想算法还是背的?
好像不对吧?
比如最简单情况
11111111111111111111
1 1
1 1
1 1
11111111111111111111
中间都是零。
按照算法,不能给出正确答案啊。因为(i,j)不能用(i-1, j)和(i, j-1)的子问题构建。
[j
【在 a********g 的大作中提到】 : 用动态规划. : 开个m*n的额外空间. : 每个cell有个row和col值 : if arr[i][j] != 0 : row[i][j] 和 col [i][j] : 有三个候选项: : 1) row[i][j] = row[i-1][j] +1; col[i][j] = 1; : 2) col[i][j] = col[i][j-1]; row[i][j] = 1; : 3) row[i][j] = min(row[i-1][j], row[i][j-1]) +1 ; col[i][j] = min(col[i-1][j : ], col[i][j-1])+1;
|
d*k 发帖数: 207 | 12 O(m*n)的想了很久都不会。只有O(m*n*n)的。更好的算法请大牛来补充吧。
事先计算好对于每个点,向上最多有都少个连续的1,若当前点为0,则记录0。设记录
数组为height。
枚举最优解的底边(0~m-1)和高(1~n-1),共O(m*n)种。设当前底边为a, 上边为b, h
= b - a + 1。扫描i = 0..n-1。找到连续的a[i] == b[i] == 1的区间。对于每个区
间[p, q],令l = p, r = q。每次l++, r--,直到找到第一个height[a][l] >= h &&
height[a][r] >= h && l <= r 的l, r。这是一个可行解,面积为(r - l + 1) * h。
如此扫描的时间代价是O(n)。
因此总时间复杂度为m*n*n
height可以优化成一个数组height[n],用最大全1子矩阵的方法更新,相当于那个“直
方图”。
欢迎大家拍砖。
【在 d****n 的大作中提到】 : 就是在一个MXN的0/1 矩阵中找边全是1的最大矩形,有没有O(MN)的解法呀?
|