求Leetcode OJ Maximal Rectangle的n^2解法# JobHunting - 待字闺中
w*x
1 楼
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle
containing all ones and return its area.
containing all ones and return its area.
l*c
2 楼
这题我理解不了，largest不就是matrix本身了吗
f*t
3 楼
是要里面全部为1
【在 l****c 的大作中提到】
: 这题我理解不了，largest不就是matrix本身了吗
【在 l****c 的大作中提到】
: 这题我理解不了，largest不就是matrix本身了吗
s*s
4 楼
这道题目是另一个问题的升级，
基础题目是这样的：
表中有若干柱状图，问最大包含在柱状图内的矩形。
这个题目可以用自左到右的堆栈解决，复杂度O(N）
然后上面的题目就是假设有N行，上界是1，下界是1..N
划归成上面的基础题目解决，复杂度O(N^2)
基础题目是这样的：
表中有若干柱状图，问最大包含在柱状图内的矩形。
这个题目可以用自左到右的堆栈解决，复杂度O(N）
然后上面的题目就是假设有N行，上界是1，下界是1..N
划归成上面的基础题目解决，复杂度O(N^2)
l*c
5 楼
哦，NOT contain all ones, but all contained are ones.
【在 f*******t 的大作中提到】
: 是要里面全部为1
【在 f*******t 的大作中提到】
: 是要里面全部为1
w*x
6 楼
这题我跪了
【在 s*******s 的大作中提到】
: 这道题目是另一个问题的升级，
: 基础题目是这样的：
: 表中有若干柱状图，问最大包含在柱状图内的矩形。
: 这个题目可以用自左到右的堆栈解决，复杂度O(N）
: 然后上面的题目就是假设有N行，上界是1，下界是1..N
: 划归成上面的基础题目解决，复杂度O(N^2)
p*2
7 楼
这题一维的你会了，二维就简单了。
【在 w****x 的大作中提到】
:
: 这题我跪了
w*x
8 楼
我只知道O(n^3)的, 这题居然能抽象成histogram, 这是多么强大的思维能力阿~~~
【在 p*****2 的大作中提到】
:
: 这题一维的你会了，二维就简单了。
p*2
9 楼
没办法呀。牛人咱比不了呀。昨天那题解的也很牛X呀。一看就不是一般人。
【在 w****x 的大作中提到】
:
: 我只知道O(n^3)的, 这题居然能抽象成histogram, 这是多么强大的思维能力阿~~~
t*7
10 楼
这题就是变相求直方图中的最大面积矩形吧?不过之前要确定直方图的X,Y轴,要O(n^2)
w*x
11 楼
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle
containing all ones and return its area.
containing all ones and return its area.
l*c
12 楼
这题我理解不了，largest不就是matrix本身了吗
f*t
13 楼
是要里面全部为1
【在 l****c 的大作中提到】
: 这题我理解不了，largest不就是matrix本身了吗
【在 l****c 的大作中提到】
: 这题我理解不了，largest不就是matrix本身了吗
s*s
14 楼
这道题目是另一个问题的升级，
基础题目是这样的：
表中有若干柱状图，问最大包含在柱状图内的矩形。
这个题目可以用自左到右的堆栈解决，复杂度O(N）
然后上面的题目就是假设有N行，上界是1，下界是1..N
划归成上面的基础题目解决，复杂度O(N^2)
基础题目是这样的：
表中有若干柱状图，问最大包含在柱状图内的矩形。
这个题目可以用自左到右的堆栈解决，复杂度O(N）
然后上面的题目就是假设有N行，上界是1，下界是1..N
划归成上面的基础题目解决，复杂度O(N^2)
l*c
15 楼
哦，NOT contain all ones, but all contained are ones.
【在 f*******t 的大作中提到】
: 是要里面全部为1
【在 f*******t 的大作中提到】
: 是要里面全部为1
w*x
16 楼
这题我跪了
【在 s*******s 的大作中提到】
: 这道题目是另一个问题的升级，
: 基础题目是这样的：
: 表中有若干柱状图，问最大包含在柱状图内的矩形。
: 这个题目可以用自左到右的堆栈解决，复杂度O(N）
: 然后上面的题目就是假设有N行，上界是1，下界是1..N
: 划归成上面的基础题目解决，复杂度O(N^2)
p*2
17 楼
这题一维的你会了，二维就简单了。
【在 w****x 的大作中提到】
:
: 这题我跪了
w*x
18 楼
我只知道O(n^3)的, 这题居然能抽象成histogram, 这是多么强大的思维能力阿~~~
【在 p*****2 的大作中提到】
:
: 这题一维的你会了，二维就简单了。
p*2
19 楼
没办法呀。牛人咱比不了呀。昨天那题解的也很牛X呀。一看就不是一般人。
【在 w****x 的大作中提到】
:
: 我只知道O(n^3)的, 这题居然能抽象成histogram, 这是多么强大的思维能力阿~~~
t*7
20 楼
这题就是变相求直方图中的最大面积矩形吧?不过之前要确定直方图的X,Y轴,要O(n^2)
z*2
21 楼
还好吧。。。是挺难想的。。。不过也没那么变态 毕竟两题在一起。。。的确容易联
系起来 不过联系起来了也很难完整的写出来
【在 w****x 的大作中提到】
:
: 我只知道O(n^3)的, 这题居然能抽象成histogram, 这是多么强大的思维能力阿~~~
h*i
22 楼
还好，我做的时候也想到了。不过面试的时候最好写O(n^3)，否则一看就是做过。
【在 w****x 的大作中提到】
:
: 我只知道O(n^3)的, 这题居然能抽象成histogram, 这是多么强大的思维能力阿~~~
【在 w****x 的大作中提到】
:
: 我只知道O(n^3)的, 这题居然能抽象成histogram, 这是多么强大的思维能力阿~~~
f*s
23 楼
N^3的方法是怎样的？
我只知道不一定全为一的那个可以N^3， 全为1的矩阵（不是方阵）的怎么搞？
【在 h***i 的大作中提到】
: 还好，我做的时候也想到了。不过面试的时候最好写O(n^3)，否则一看就是做过。
我只知道不一定全为一的那个可以N^3， 全为1的矩阵（不是方阵）的怎么搞？
【在 h***i 的大作中提到】
: 还好，我做的时候也想到了。不过面试的时候最好写O(n^3)，否则一看就是做过。
p*2
24 楼
这次黑客杯第一轮的最后一题跟这个很类似。
http://blog.sina.com.cn/s/blog_b9285de20101ibbh.html
http://blog.sina.com.cn/s/blog_b9285de20101ibbh.html
z*2
25 楼
还好吧。。。是挺难想的。。。不过也没那么变态 毕竟两题在一起。。。的确容易联
系起来 不过联系起来了也很难完整的写出来
【在 w****x 的大作中提到】
:
: 我只知道O(n^3)的, 这题居然能抽象成histogram, 这是多么强大的思维能力阿~~~
h*i
26 楼
还好，我做的时候也想到了。不过面试的时候最好写O(n^3)，否则一看就是做过。
【在 w****x 的大作中提到】
:
: 我只知道O(n^3)的, 这题居然能抽象成histogram, 这是多么强大的思维能力阿~~~
【在 w****x 的大作中提到】
:
: 我只知道O(n^3)的, 这题居然能抽象成histogram, 这是多么强大的思维能力阿~~~
f*s
27 楼
N^3的方法是怎样的？
我只知道不一定全为一的那个可以N^3， 全为1的矩阵（不是方阵）的怎么搞？
【在 h***i 的大作中提到】
: 还好，我做的时候也想到了。不过面试的时候最好写O(n^3)，否则一看就是做过。
我只知道不一定全为一的那个可以N^3， 全为1的矩阵（不是方阵）的怎么搞？
【在 h***i 的大作中提到】
: 还好，我做的时候也想到了。不过面试的时候最好写O(n^3)，否则一看就是做过。
p*2
28 楼
这次黑客杯第一轮的最后一题跟这个很类似。
http://blog.sina.com.cn/s/blog_b9285de20101ibbh.html
http://blog.sina.com.cn/s/blog_b9285de20101ibbh.html
z*2
29 楼
B*t
30 楼
class Solution {
public:
int maximalRectangle(vector > &matrix) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(!matrix.size())
return 0;
int start, largest = 0;
vector left(matrix[0].size(), 0);
vector right(matrix[0].size(), 0);
vector height(matrix[0].size(), 0);
for(int i = 0; i < matrix.size(); i++)
{
left[0] = 0;
right[matrix[0].size() - 1] = matrix[0].size() - 1;
for(int j = 0; j < matrix[0].size(); j++)
if(matrix[i][j] == '1')
height[j] += 1;
else
height[j] = 0;
for(int j = 1; j < matrix[0].size(); j++)
{
start = j;
while(start > 0 && height[j] <= height[start-1])
start = left[start-1];
left[j] = start;
}
for(int j = matrix[0].size() - 2; j >= 0; j--)
{
start = j;
while(start < height.size()-1 && height[j] <= height[start+1
])
start = right[start+1];
right[j] = start;
}
for(int j = 0; j < matrix[0].size(); j++)
{
int temp = (right[j] - left[j] + 1) * height[j];
if(temp > largest)
largest = temp;
}
}
return largest;
}
};
rectangle
【在 w****x 的大作中提到】
: Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle
: containing all ones and return its area.
public:
int maximalRectangle(vector
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(!matrix.size())
return 0;
int start, largest = 0;
vector
vector
vector
for(int i = 0; i < matrix.size(); i++)
{
left[0] = 0;
right[matrix[0].size() - 1] = matrix[0].size() - 1;
for(int j = 0; j < matrix[0].size(); j++)
if(matrix[i][j] == '1')
height[j] += 1;
else
height[j] = 0;
for(int j = 1; j < matrix[0].size(); j++)
{
start = j;
while(start > 0 && height[j] <= height[start-1])
start = left[start-1];
left[j] = start;
}
for(int j = matrix[0].size() - 2; j >= 0; j--)
{
start = j;
while(start < height.size()-1 && height[j] <= height[start+1
])
start = right[start+1];
right[j] = start;
}
for(int j = 0; j < matrix[0].size(); j++)
{
int temp = (right[j] - left[j] + 1) * height[j];
if(temp > largest)
largest = temp;
}
}
return largest;
}
};
rectangle
【在 w****x 的大作中提到】
: Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle
: containing all ones and return its area.
c*7
31 楼
你贴的是square sub-matrix
leetcode是要retangle
【在 z***2 的大作中提到】
: http://www.geeksforgeeks.org/maximum-size-sub-matrix-with-all-1
: 貌似最优的n^2解法
leetcode是要retangle
【在 z***2 的大作中提到】
: http://www.geeksforgeeks.org/maximum-size-sub-matrix-with-all-1
: 貌似最优的n^2解法
N*D
32 楼
都搞这么牛的题了，太牛了
【在 c****7 的大作中提到】
: 你贴的是square sub-matrix
: leetcode是要retangle
【在 c****7 的大作中提到】
: 你贴的是square sub-matrix
: leetcode是要retangle
c*e
33 楼
有人能讲一下O(n^3)的解法吗？
f*t
34 楼
面试时不会问这么难的
【在 N*D 的大作中提到】
: 都搞这么牛的题了，太牛了
【在 N*D 的大作中提到】
: 都搞这么牛的题了，太牛了
c*7
35 楼
靠，你们不都是在看leetcode嘛！
我基本都不是做题，就是看别人怎么做，死记硬背下来～～
【在 N*D 的大作中提到】
: 都搞这么牛的题了，太牛了
我基本都不是做题，就是看别人怎么做，死记硬背下来～～
【在 N*D 的大作中提到】
: 都搞这么牛的题了，太牛了
相关阅读
川粉傻眼了 川普取消OPT extemsion (转载)理工男从硅谷海归 如今估值已达3亿美元zt (转载)My dayjob 'll finish in 2 wks求 Google team match求指点 WalmartLab v.s. Yahoo关于老中的上班睡觉和听报告玩手机气床家那个面试cross function是啥面试啊工作签证改革方向来了，重大利好中国留学生 (转载)【工作机会&内推】Cisco @ Atlanta求leetcode转让Onsite interview后一般多久内收到消息啊？祝大家新年发大财用人单位搞错对象了找底层软件工作一年未果...怎么能拿到Google Offer ?三哥是在美华人无法预约的高峰 (转载)别转machine learning，坚守马工公司面试，对方HR邀我住到她家里过夜，常见么？full stack engineer 真 TM 坑爹请问大家一个背景调查的问题