g*********s
发帖数: 1782 | 1 I'm not talking about the O(N) dp solution, but the O(NlogN) one based on
the order-statistic tree here:
http://blog.csdn.net/arbuckle/archive/2006/05/06/710988.aspx | b*****e
发帖数: 474 | 2 我来抛砖吧。
O(n) 的解法大家都知道了吧。这个是O(n log n)的，比较直观点，
就是简单的Divide & Conquer，分别计算前半和后半的最大矩形面积，
然后和贯穿中间的最大矩形比较面积。我用最普通的前后扫描方法
来确定贯穿中间的最大矩形面积（O(n)时间）。所以这个算法和
MergeSort的情形一样，都是分成两个一半大小的子问题，然后O(n)
时间来合成。所以是O(nlogn)。
Java 程序：
public class histo {
public static int maxRect(int[] table ) {
return maxRect(table, 0, table.length-1);
}
public static int maxRect(int[] table, int start, int end) {
if ( start == end ) return table[start];
if ( start == end-1)
return Math.max(Math.max(table[end],table[start]),
2*Math.min(table[end],table[start]));
int mid = (start+end)/2;
int max = Math.max(maxRect(table, start, mid-1),
maxRect(table, mid+1, end));
int i= mid-1;
int j= mid+1;
int height = table[mid];
int area = 0;
while ( true ) {
while ( i>=start && table[i] >= height ) i--;
while ( j<=end && table[j] >= height ) j++;
area = height * ( j-i - 1) ;
if ( area > max ) max = area;
if ( i>=start && j<=end ) {
height = Math.max(table[i], table[j]);
} else if ( iend ) {
break;
} else if ( i< start ) {
height = table[j];
} else { // ( j > end )
height = table[i];
}
}
return max;
}
public static void main(String[] args) {
int [] a = { 2, 1, 4, 5, 1, 3, 3 };
System.out.println( maxRect(a) );
}
} | D***h
发帖数: 183 | 3 显然是错的.
横跨两边的最大Rect高度可能比最中间那个小。
【在 b*****e 的大作中提到】
: 我来抛砖吧。
: O(n) 的解法大家都知道了吧。这个是O(n log n)的，比较直观点，
: 就是简单的Divide & Conquer，分别计算前半和后半的最大矩形面积，
: 然后和贯穿中间的最大矩形比较面积。我用最普通的前后扫描方法
: 来确定贯穿中间的最大矩形面积（O(n)时间）。所以这个算法和
: MergeSort的情形一样，都是分成两个一半大小的子问题，然后O(n)
: 时间来合成。所以是O(nlogn)。
: Java 程序：
: public class histo {
: public static int maxRect(int[] table ) {
| b*****e
发帖数: 474 | 4 考虑到了的。可能我说得简单了点。
看看Code里关于height的那一段你就明白了。
【在 D***h 的大作中提到】
: 显然是错的.
: 横跨两边的最大Rect高度可能比最中间那个小。
| t*****j
发帖数: 1105 | 5 这道题我onsite碰到了，结果脑袋短路，只给出了O（n2）解法，回家后一想
就想到你这个解法了，一点都不难，不知道为啥当场没想出来，郁闷死了。
可能是给的时间短了点，20分钟左右要理解题目再写出code并且给出复杂度。
我后悔死没带笔记本去onsite了，白板写code又慢又累又难看。面试完右胳膊
都酸的要死，不知道是不是因为我个子不高，老要伸高写字的缘故。
发现当场面试时候要想发挥好也挺不容易的，难免有这个那个疏忽之处。
【在 b*****e 的大作中提到】
: 我来抛砖吧。
: O(n) 的解法大家都知道了吧。这个是O(n log n)的，比较直观点，
: 就是简单的Divide & Conquer，分别计算前半和后半的最大矩形面积，
: 然后和贯穿中间的最大矩形比较面积。我用最普通的前后扫描方法
: 来确定贯穿中间的最大矩形面积（O(n)时间）。所以这个算法和
: MergeSort的情形一样，都是分成两个一半大小的子问题，然后O(n)
: 时间来合成。所以是O(nlogn)。
: Java 程序：
: public class histo {
: public static int maxRect(int[] table ) {
| g*********s
发帖数: 1782 | 6 The D&C idea is easy to understand.
But to obtain the optimal results, how can you guarantee the partition is
always half to half to make sure T(N) = 2T(N/2) + N holds?
Someone made a valid challenge earlier.
【在 b*****e 的大作中提到】
: 我来抛砖吧。
: O(n) 的解法大家都知道了吧。这个是O(n log n)的，比较直观点，
: 就是简单的Divide & Conquer，分别计算前半和后半的最大矩形面积，
: 然后和贯穿中间的最大矩形比较面积。我用最普通的前后扫描方法
: 来确定贯穿中间的最大矩形面积（O(n)时间）。所以这个算法和
: MergeSort的情形一样，都是分成两个一半大小的子问题，然后O(n)
: 时间来合成。所以是O(nlogn)。
: Java 程序：
: public class histo {
: public static int maxRect(int[] table ) {
| g*********s
发帖数: 1782 | 7 No, I don't see how your code can handle it.
【在 b*****e 的大作中提到】
: 考虑到了的。可能我说得简单了点。
: 看看Code里关于height的那一段你就明白了。
| t*****j
发帖数: 1105 | 8 做好情况O(nlgn),最差情况还是O（n2）。
is
【在 g*********s 的大作中提到】
: The D&C idea is easy to understand.
: But to obtain the optimal results, how can you guarantee the partition is
: always half to half to make sure T(N) = 2T(N/2) + N holds?
: Someone made a valid challenge earlier.
| b*****e
发帖数: 474 | 9 1) 我采用的是对分法，mid = (start+end)/2。当然是 2 T(n/2) 了
2) 这个。。。 很容易自己验证一下嘛。代码都给出了，有疑问的话，
构造一组输入，比如
int a[] = { 1,1,1,1,1,1,1,4,4,4,1,1,1,1,1,1 }; // 答案是16
看看和心目中所想是不是一样。
【在 g*********s 的大作中提到】
: No, I don't see how your code can handle it.
| g*********s
发帖数: 1782 | 10 no, i don't get it. ur half-cut method is different with what I posted.
in addition, i don't think one test case can justify the correctness
algorithm.
can u verbally describe ur idea? the key is how to maintain the optimality
when u merge the 1st/2nd half optimal solution and the optimal solution
crossing the pivot.
【在 b*****e 的大作中提到】
: 1) 我采用的是对分法，mid = (start+end)/2。当然是 2 T(n/2) 了
: 2) 这个。。。 很容易自己验证一下嘛。代码都给出了，有疑问的话，
: 构造一组输入，比如
: int a[] = { 1,1,1,1,1,1,1,4,4,4,1,1,1,1,1,1 }; // 答案是16
: 看看和心目中所想是不是一样。
| | | a****d
发帖数: 114 | 11 能说一下 O(n)的算法么？
【在 g*********s 的大作中提到】
: I'm not talking about the O(N) dp solution, but the O(NlogN) one based on
: the order-statistic tree here:
: http://blog.csdn.net/arbuckle/archive/2006/05/06/710988.aspx
| b*****e
发帖数: 474 | 12 OK, 左右两半的最大矩形面积可用递归得到，不多说了。
横跨中间的矩形，最高就是 height = table[mid], 长度可以向两边
搜索得到。
搜索过程中，或者遇到边界，或者在遇到边界前碰到降低的高度。这个时候
就取下一个最高的高度，然后继续向两边搜索在新高度下的最大边长。
这个过程中记录下最大面积的那个就行了。
这个从中间向两边搜索的过程有点像 merge-sort 里的 merge 过程，是
个简单的 O(n) 过程。
【在 g*********s 的大作中提到】
: no, i don't get it. ur half-cut method is different with what I posted.
: in addition, i don't think one test case can justify the correctness
: algorithm.
: can u verbally describe ur idea? the key is how to maintain the optimality
: when u merge the 1st/2nd half optimal solution and the optimal solution
: crossing the pivot.
| g*********s
发帖数: 1782 | 13 你这样解释一下就对了。这个方法可行，不过和我原帖的思路不一样。
【在 b*****e 的大作中提到】
: OK, 左右两半的最大矩形面积可用递归得到，不多说了。
: 横跨中间的矩形，最高就是 height = table[mid], 长度可以向两边
: 搜索得到。
: 搜索过程中，或者遇到边界，或者在遇到边界前碰到降低的高度。这个时候
: 就取下一个最高的高度，然后继续向两边搜索在新高度下的最大边长。
: 这个过程中记录下最大面积的那个就行了。
: 这个从中间向两边搜索的过程有点像 merge-sort 里的 merge 过程，是
: 个简单的 O(n) 过程。
| l******y
发帖数: 472 | 14 有谁能讲讲那个用stack做的O(n)的算法么？上面的链接里说的没看明白
还有请问lz，dp做到O(n) ? thanks | j********x
发帖数: 2330 | 15 自己run一遍就看出来了，很难讲清楚
【在 l******y 的大作中提到】
: 有谁能讲讲那个用stack做的O(n)的算法么？上面的链接里说的没看明白
: 还有请问lz，dp做到O(n) ? thanks
|
|
