c**********e
发帖数: 2007 | 1 1. How to find the maximum rectangular in a histogram. You have the heights
of the histogram H[i], i=1,...,N.
2. Give a matrix x[i][j], i,j=1,...,N, which contain 0, 1 only. How to find
the maximum rectangular which contain 0 only. | A*********r
发帖数: 564 | 2 都是DP.
第一个很简单，对每一个高度，分别记录能够到达的最左和最右的坐标，最后最大的那个就是。。
Let L(i)=R(i)=i at first, then
更新 L(i)=L(i-1) while H[i]<=H[j] j=i-1..0
更新 R(i)=R(i+1) while H[i]<=H[j] j=i+1..n
最后max { H[i]*(R(i)-L(i)) } 就是最大的矩形。这个算法不是最优的。。
第二个比较复杂，brute force 估计要用O(n^3), 最好貌似可以做到O(n^2).
参见 http://www.drdobbs.com/184410529
heights
find
【在 c**********e 的大作中提到】
: 1. How to find the maximum rectangular in a histogram. You have the heights
: of the histogram H[i], i=1,...,N.
: 2. Give a matrix x[i][j], i,j=1,...,N, which contain 0, 1 only. How to find
: the maximum rectangular which contain 0 only.
| c****l
发帖数: 1280 | 3
=> what does it mean by maximum here? the length or the area? thanks
【在 A*********r 的大作中提到】
: 都是DP.
: 第一个很简单，对每一个高度，分别记录能够到达的最左和最右的坐标，最后最大的那个就是。。
: Let L(i)=R(i)=i at first, then
: 更新 L(i)=L(i-1) while H[i]<=H[j] j=i-1..0
: 更新 R(i)=R(i+1) while H[i]<=H[j] j=i+1..n
: 最后max { H[i]*(R(i)-L(i)) } 就是最大的矩形。这个算法不是最优的。。
: 第二个比较复杂，brute force 估计要用O(n^3), 最好貌似可以做到O(n^2).
: 参见 http://www.drdobbs.com/184410529
:
: heights
| A*********r
发帖数: 564 | 4 谢谢提醒，应该是面积，忘了乘上H[i]了，已经改了。。
【在 c****l 的大作中提到】
:
: => what does it mean by maximum here? the length or the area? thanks
| h**k
发帖数: 3368 | 5 第一题的算法不对。按你这个思路，对于H[i]，你必须比较所有的H[j]和H[i]，来找到
高度为H[i]的矩形的左右边界。这样复杂度是O(n^2)。正确算法是用stack。
第二题的brute force是O(n^6)，最后利用第一题的思路，可以到O(n^2)。
【在 A*********r 的大作中提到】
: 都是DP.
: 第一个很简单，对每一个高度，分别记录能够到达的最左和最右的坐标，最后最大的那个就是。。
: Let L(i)=R(i)=i at first, then
: 更新 L(i)=L(i-1) while H[i]<=H[j] j=i-1..0
: 更新 R(i)=R(i+1) while H[i]<=H[j] j=i+1..n
: 最后max { H[i]*(R(i)-L(i)) } 就是最大的矩形。这个算法不是最优的。。
: 第二个比较复杂，brute force 估计要用O(n^3), 最好貌似可以做到O(n^2).
: 参见 http://www.drdobbs.com/184410529
:
: heights
| l**o
发帖数: 356 | 6 1.我用递归做的:
遍历整个数组,找到最小值min,
返回max(min*len,min左边一半数组的最大矩形,min右边一半数组的最大矩形)
heights
find
【在 c**********e 的大作中提到】
: 1. How to find the maximum rectangular in a histogram. You have the heights
: of the histogram H[i], i=1,...,N.
: 2. Give a matrix x[i][j], i,j=1,...,N, which contain 0, 1 only. How to find
: the maximum rectangular which contain 0 only.
| l**o
发帖数: 356 | 7 第二道我是这么做的:
对于数组中每一行:
遇到0,则为前面一个加一,遇到1则清零
e.g.0011010->1200101
在得到的二维矩阵里,对每一个数竖着看,算出每个对应的最大值
e.g.
2
3
4
5
->9
heights
find
【在 c**********e 的大作中提到】
: 1. How to find the maximum rectangular in a histogram. You have the heights
: of the histogram H[i], i=1,...,N.
: 2. Give a matrix x[i][j], i,j=1,...,N, which contain 0, 1 only. How to find
: the maximum rectangular which contain 0 only.
| h**k
发帖数: 3368 | 8 worst case O(n^2), if you need O(n) to find a minimum value
【在 l**o 的大作中提到】
: 1.我用递归做的:
: 遍历整个数组,找到最小值min,
: 返回max(min*len,min左边一半数组的最大矩形,min右边一半数组的最大矩形)
:
: heights
: find
|
| p********7
发帖数: 549 | | A*********r
发帖数: 564 | 10 谢谢指正，赶紧回去查了一下前几天看的DP网页, 上面赫然写着O(n)，害我想当然以为
这就是最优解，没有去仔细推导算法复杂度。。唉，还是自己理解不够深刻。。
第二题你能大概说说么？
【在 h**k 的大作中提到】
: 第一题的算法不对。按你这个思路，对于H[i]，你必须比较所有的H[j]和H[i]，来找到
: 高度为H[i]的矩形的左右边界。这样复杂度是O(n^2)。正确算法是用stack。
: 第二题的brute force是O(n^6)，最后利用第一题的思路，可以到O(n^2)。
| c**********e
发帖数: 2007 | 11 Which DP网页?
【在 A*********r 的大作中提到】
: 谢谢指正，赶紧回去查了一下前几天看的DP网页, 上面赫然写着O(n)，害我想当然以为
: 这就是最优解，没有去仔细推导算法复杂度。。唉，还是自己理解不够深刻。。
: 第二题你能大概说说么？
|
|
