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 的大作中提到】
: 用动态规划.
: 开个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 的大作中提到】
: 用动态规划.
: 开个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 的大作中提到】
: 就是在一个MXN的0/1 矩阵中找边全是1的最大矩形，有没有O(MN)的解法呀？
在每一行基于当前高度找LargestArea
然后对于每一行找到的最大面积找整个矩阵的最大面积。
参考：
http://yyeclipse.blogspot.com/2012/11/solving-maximal-rectangle
【在 d****n 的大作中提到】
: 就是在一个MXN的0/1 矩阵中找边全是1的最大矩形，有没有O(MN)的解法呀？
m*e
5 楼
再加一道类似的题：同样的矩阵，找最大的子方阵。这个方阵的长宽一样，每个元素都
要是1。
【在 m**********e 的大作中提到】
: 需要用到一个帮助矩阵。
: 在每一行基于当前高度找LargestArea
: 然后对于每一行找到的最大面积找整个矩阵的最大面积。
: 参考：
: http://yyeclipse.blogspot.com/2012/11/solving-maximal-rectangle
要是1。
【在 m**********e 的大作中提到】
: 需要用到一个帮助矩阵。
: 在每一行基于当前高度找LargestArea
: 然后对于每一行找到的最大面积找整个矩阵的最大面积。
: 参考：
: http://yyeclipse.blogspot.com/2012/11/solving-maximal-rectangle
d*n
6 楼
link里的跟这题不是一道题。 这是最大黑边矩形问题。
【在 m**********e 的大作中提到】
: 需要用到一个帮助矩阵。
: 在每一行基于当前高度找LargestArea
: 然后对于每一行找到的最大面积找整个矩阵的最大面积。
: 参考：
: http://yyeclipse.blogspot.com/2012/11/solving-maximal-rectangle
【在 m**********e 的大作中提到】
: 需要用到一个帮助矩阵。
: 在每一行基于当前高度找LargestArea
: 然后对于每一行找到的最大面积找整个矩阵的最大面积。
: 参考：
: http://yyeclipse.blogspot.com/2012/11/solving-maximal-rectangle
l*n
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)的解法呀？
然后用histogram最大面积的o(n)算法处理每一行.
【在 d****n 的大作中提到】
: 就是在一个MXN的0/1 矩阵中找边全是1的最大矩形，有没有O(MN)的解法呀？
a*g
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;
[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
9 楼
算正方形是更容易的 DP...
【在 m**********e 的大作中提到】
: 再加一道类似的题：同样的矩阵，找最大的子方阵。这个方阵的长宽一样，每个元素都
: 要是1。
【在 m**********e 的大作中提到】
: 再加一道类似的题：同样的矩阵，找最大的子方阵。这个方阵的长宽一样，每个元素都
: 要是1。
d*n
10 楼
你们讨论的都不着题呀， 这要是真面时这样就得跪了。
【在 s*****r 的大作中提到】
: 算正方形是更容易的 DP...
【在 s*****r 的大作中提到】
: 算正方形是更容易的 DP...
d*k
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;
好像不对吧？
比如最简单情况
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
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)的解法呀？
事先计算好对于每个点，向上最多有都少个连续的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)的解法呀？
相关阅读
我们这里油价已经低于2.5美金了你还在考cfa？大数据都“占领华尔街了”！求解释丽寇儿的新题maximum gap题目到底啥意思？broadcom，irvine，senior staff package的RSU只有25K，是不是可怜了点？觉得100K才像话？这种情况我该选哪一个公司FB面经求问一个offer选择为啥技术牛的公司不怎么挣钱g家工资每年大概能涨多少？argue工资，是涨salary好还是多要点RSU？RSU是不是交税少？*** 急招Python程序员 | 洛杉矶 | 各种程度 ***onsite 被问现在的薪水和预期的薪水 请问怎么回答？请问到底怎么刷题呀？p2p lending比较火啊：https://blendlabs.com/从技术角度来看，google确实第一老东家的hr非叫我把假期用掉求问 HR如果要reference 必须某个系的TSC的OPT申请状态怎么一点动静也没有G的一道Onesite题rumor说qcom明年还要裁千人以上?