w****x
发帖数: 2483 | 1 Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle
containing all ones and return its area. |
l****c
发帖数: 782 | 2 这题我理解不了，largest不就是matrix本身了吗 |
f*******t
发帖数: 7549 | 3 是要里面全部为1
【在 l****c 的大作中提到】
: 这题我理解不了，largest不就是matrix本身了吗
|
s*******s
发帖数: 46 | 4 这道题目是另一个问题的升级，
基础题目是这样的：
表中有若干柱状图，问最大包含在柱状图内的矩形。
这个题目可以用自左到右的堆栈解决，复杂度O(N）
然后上面的题目就是假设有N行，上界是1，下界是1..N
划归成上面的基础题目解决，复杂度O(N^2) |
l****c
发帖数: 782 | 5 哦，NOT contain all ones, but all contained are ones.
【在 f*******t 的大作中提到】
: 是要里面全部为1
|
w****x
发帖数: 2483 | 6
这题我跪了
【在 s*******s 的大作中提到】
: 这道题目是另一个问题的升级，
: 基础题目是这样的：
: 表中有若干柱状图，问最大包含在柱状图内的矩形。
: 这个题目可以用自左到右的堆栈解决，复杂度O(N）
: 然后上面的题目就是假设有N行，上界是1，下界是1..N
: 划归成上面的基础题目解决，复杂度O(N^2)
|
p*****2
发帖数: 21240 | 7
这题一维的你会了，二维就简单了。
【在 w****x 的大作中提到】
:
: 这题我跪了
|
w****x
发帖数: 2483 | 8
我只知道O(n^3)的, 这题居然能抽象成histogram, 这是多么强大的思维能力阿~~~
【在 p*****2 的大作中提到】
:
: 这题一维的你会了，二维就简单了。
|
p*****2
发帖数: 21240 | 9
没办法呀。牛人咱比不了呀。昨天那题解的也很牛X呀。一看就不是一般人。
【在 w****x 的大作中提到】
:
: 我只知道O(n^3)的, 这题居然能抽象成histogram, 这是多么强大的思维能力阿~~~
|
t*********7
发帖数: 255 | 10 这题就是变相求直方图中的最大面积矩形吧?不过之前要确定直方图的X,Y轴,要O(n^2) |
|
|
w****x
发帖数: 2483 | 11 Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle
containing all ones and return its area. |
l****c
发帖数: 782 | 12 这题我理解不了，largest不就是matrix本身了吗 |
f*******t
发帖数: 7549 | 13 是要里面全部为1
【在 l****c 的大作中提到】
: 这题我理解不了，largest不就是matrix本身了吗
|
s*******s
发帖数: 46 | 14 这道题目是另一个问题的升级，
基础题目是这样的：
表中有若干柱状图，问最大包含在柱状图内的矩形。
这个题目可以用自左到右的堆栈解决，复杂度O(N）
然后上面的题目就是假设有N行，上界是1，下界是1..N
划归成上面的基础题目解决，复杂度O(N^2) |
l****c
发帖数: 782 | 15 哦，NOT contain all ones, but all contained are ones.
【在 f*******t 的大作中提到】
: 是要里面全部为1
|
w****x
发帖数: 2483 | 16
这题我跪了
【在 s*******s 的大作中提到】
: 这道题目是另一个问题的升级，
: 基础题目是这样的：
: 表中有若干柱状图，问最大包含在柱状图内的矩形。
: 这个题目可以用自左到右的堆栈解决，复杂度O(N）
: 然后上面的题目就是假设有N行，上界是1，下界是1..N
: 划归成上面的基础题目解决，复杂度O(N^2)
|
p*****2
发帖数: 21240 | 17
这题一维的你会了，二维就简单了。
【在 w****x 的大作中提到】
:
: 这题我跪了
|
w****x
发帖数: 2483 | 18
我只知道O(n^3)的, 这题居然能抽象成histogram, 这是多么强大的思维能力阿~~~
【在 p*****2 的大作中提到】
:
: 这题一维的你会了，二维就简单了。
|
p*****2
发帖数: 21240 | 19
没办法呀。牛人咱比不了呀。昨天那题解的也很牛X呀。一看就不是一般人。
【在 w****x 的大作中提到】
:
: 我只知道O(n^3)的, 这题居然能抽象成histogram, 这是多么强大的思维能力阿~~~
|
t*********7
发帖数: 255 | 20 这题就是变相求直方图中的最大面积矩形吧?不过之前要确定直方图的X,Y轴,要O(n^2) |
|
|
z***2
发帖数: 3 | 21
还好吧。。。是挺难想的。。。不过也没那么变态 毕竟两题在一起。。。的确容易联
系起来 不过联系起来了也很难完整的写出来
【在 w****x 的大作中提到】
:
: 我只知道O(n^3)的, 这题居然能抽象成histogram, 这是多么强大的思维能力阿~~~
|
h***i
发帖数: 1970 | 22 还好，我做的时候也想到了。不过面试的时候最好写O(n^3)，否则一看就是做过。
【在 w****x 的大作中提到】
:
: 我只知道O(n^3)的, 这题居然能抽象成histogram, 这是多么强大的思维能力阿~~~
|
f****s
发帖数: 74 | 23 N^3的方法是怎样的？
我只知道不一定全为一的那个可以N^3， 全为1的矩阵（不是方阵）的怎么搞？
【在 h***i 的大作中提到】
: 还好，我做的时候也想到了。不过面试的时候最好写O(n^3)，否则一看就是做过。
|
p*****2
发帖数: 21240 | |
z***2
发帖数: 3 | 25
还好吧。。。是挺难想的。。。不过也没那么变态 毕竟两题在一起。。。的确容易联
系起来 不过联系起来了也很难完整的写出来
【在 w****x 的大作中提到】
:
: 我只知道O(n^3)的, 这题居然能抽象成histogram, 这是多么强大的思维能力阿~~~
|
h***i
发帖数: 1970 | 26 还好，我做的时候也想到了。不过面试的时候最好写O(n^3)，否则一看就是做过。
【在 w****x 的大作中提到】
:
: 我只知道O(n^3)的, 这题居然能抽象成histogram, 这是多么强大的思维能力阿~~~
|
f****s
发帖数: 74 | 27 N^3的方法是怎样的？
我只知道不一定全为一的那个可以N^3， 全为1的矩阵（不是方阵）的怎么搞？
【在 h***i 的大作中提到】
: 还好，我做的时候也想到了。不过面试的时候最好写O(n^3)，否则一看就是做过。
|
p*****2
发帖数: 21240 | |
z***2
发帖数: 3 | |
B********t
发帖数: 147 | 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.
|
|
|
c****7
发帖数: 4192 | 31 你贴的是square sub-matrix
leetcode是要retangle
【在 z***2 的大作中提到】
: http://www.geeksforgeeks.org/maximum-size-sub-matrix-with-all-1
: 貌似最优的n^2解法
|
N*D
发帖数: 3641 | 32 都搞这么牛的题了，太牛了
【在 c****7 的大作中提到】
: 你贴的是square sub-matrix
: leetcode是要retangle
|
c***e
发帖数: 542 | |
f*******t
发帖数: 7549 | 34 面试时不会问这么难的
【在 N*D 的大作中提到】
: 都搞这么牛的题了，太牛了
|
c****7
发帖数: 4192 | 35 靠，你们不都是在看leetcode嘛！
我基本都不是做题，就是看别人怎么做，死记硬背下来～～
【在 N*D 的大作中提到】
: 都搞这么牛的题了，太牛了
|
