a*g
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最大的那一个候选项.
这个需要画个图就比较容易想清楚,说明白.
开个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
3 楼
谢了,不过没太看懂。
[j
【在 a********g 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: 用动态规划.
: 开个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;
[j
【在 a********g 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 用动态规划.
: 开个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
4 楼
需要用到一个帮助矩阵。
在每一行基于当前高度找LargestArea
然后对于每一行找到的最大面积找整个矩阵的最大面积。
参考:
http://yyeclipse.blogspot.com/2012/11/solving-maximal-rectangle
【在 d****n 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: 就是在一个MXN的0/1 矩阵中找边全是1的最大矩形,有没有O(MN)的解法呀?
在每一行基于当前高度找LargestArea
然后对于每一行找到的最大面积找整个矩阵的最大面积。
参考:
http://yyeclipse.blogspot.com/2012/11/solving-maximal-rectangle
【在 d****n 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 就是在一个MXN的0/1 矩阵中找边全是1的最大矩形,有没有O(MN)的解法呀?
m*e
5 楼
再加一道类似的题:同样的矩阵,找最大的子方阵。这个方阵的长宽一样,每个元素都
要是1。
【在 m**********e 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: 需要用到一个帮助矩阵。
: 在每一行基于当前高度找LargestArea
: 然后对于每一行找到的最大面积找整个矩阵的最大面积。
: 参考:
: http://yyeclipse.blogspot.com/2012/11/solving-maximal-rectangle
要是1。
【在 m**********e 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 需要用到一个帮助矩阵。
: 在每一行基于当前高度找LargestArea
: 然后对于每一行找到的最大面积找整个矩阵的最大面积。
: 参考:
: http://yyeclipse.blogspot.com/2012/11/solving-maximal-rectangle
d*n
6 楼
link里的跟这题不是一道题。 这是最大黑边矩形问题。
【在 m**********e 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: 需要用到一个帮助矩阵。
: 在每一行基于当前高度找LargestArea
: 然后对于每一行找到的最大面积找整个矩阵的最大面积。
: 参考:
: http://yyeclipse.blogspot.com/2012/11/solving-maximal-rectangle
【在 m**********e 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 需要用到一个帮助矩阵。
: 在每一行基于当前高度找LargestArea
: 然后对于每一行找到的最大面积找整个矩阵的最大面积。
: 参考:
: http://yyeclipse.blogspot.com/2012/11/solving-maximal-rectangle
a*g
8 楼
这个方法可以求最大正方形。求最大矩形,需要用直方图的方法。
[j
【在 a********g 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: 用动态规划.
: 开个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;
[j
【在 a********g 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 用动态规划.
: 开个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
11 楼
自己想算法还是背的?
好像不对吧?
比如最简单情况
11111111111111111111
1 1
1 1
1 1
11111111111111111111
中间都是零。
按照算法,不能给出正确答案啊。因为(i,j)不能用(i-1, j)和(i, j-1)的子问题构建。
[j
【在 a********g 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: 用动态规划.
: 开个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;
好像不对吧?
比如最简单情况
11111111111111111111
1 1
1 1
1 1
11111111111111111111
中间都是零。
按照算法,不能给出正确答案啊。因为(i,j)不能用(i-1, j)和(i, j-1)的子问题构建。
[j
【在 a********g 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 用动态规划.
: 开个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
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 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: 就是在一个MXN的0/1 矩阵中找边全是1的最大矩形,有没有O(MN)的解法呀?
事先计算好对于每个点,向上最多有都少个连续的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 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 就是在一个MXN的0/1 矩阵中找边全是1的最大矩形,有没有O(MN)的解法呀?
相关阅读
请教: 阿里达摩院 的压缩,计算机视觉和 AI 融合现代西方发明的计算机游戏就是100 年前西方入侵中国的鸦片 (转载)Chicago SDETamazon为什么能算flag?发信接了offer, 但目前手里的工作还没做完咋办? 直接走人会不会太损人品。人生输家破釜沉舟求转型建议Expedia选组求建议Uber员工按照今天股价算 (转载)目前国内公司门槛极高,Oracle被辞退的程序员年龄大,找不到下家这样被当备胎还有戏吗?现在国内工资真心高别还没工作就退休了,致某些懒癌早期SOFI 找 java 软工大家刷题什么装备?请大家帮忙看看这non-competition究竟啥意思。。。如何准备教职面试中的演讲【工作机会】Boston 金融公司Invesco招Sr. Frontend Javascript Developer最近有面facebook吗extreme networks这个公司怎么样?Samsung Software engineer 的内推。