c********t
发帖数: 5706 | 1 想了一个笨的O(n*logn)方法
1.找到从begin到end最小值min, 得到index_min
2.则从begin index到 end index的rectangle area = min*(end-begin+1)。
3.用recursion重复1,2，计算[begin，index_min-1] 的rectangle面积和[index_min+1
,end]的面积。
过了small test, large test 在[0,1...19999]的例子，得到runtime error。
拷到eclipse测试，通过了。谁能帮我看看有什么问题。
public class Solution {
int max;
public int largestRectangleArea(int[] height) {
// Start typing your Java solution below
// DO NOT write main() function
max = 0;
if(height == null || height.length == 0) return 0;
largest(height, 0, height.length-1);
return max;
}
public void largest(int[] height, int begin, int end){
if(begin==end) {
max= Math.max(max,height[begin]);
return;
}
int min = Integer.MAX_VALUE, index_min=0;
for(int i= begin; i<=end; i++){
if(height[i] < min){
min = height[i];
index_min=i;
}
}
max= Math.max(max, min*(end-begin+1));
if(index_min == begin) largest(height, index_min+1, end);
else if(index_min == end) largest(height, begin, index_min-1);
else{
largest(height, begin, index_min-1);
largest(height, index_min+1, end);
}
}
} | l*******b
发帖数: 2586 | 2 递归太深，stack 爆了？
+1
【在 c********t 的大作中提到】
: 想了一个笨的O(n*logn)方法
: 1.找到从begin到end最小值min, 得到index_min
: 2.则从begin index到 end index的rectangle area = min*(end-begin+1)。
: 3.用recursion重复1,2，计算[begin，index_min-1] 的rectangle面积和[index_min+1
: ,end]的面积。
: 过了small test, large test 在[0,1...19999]的例子，得到runtime error。
: 拷到eclipse测试，通过了。谁能帮我看看有什么问题。
: public class Solution {
: int max;
: public int largestRectangleArea(int[] height) {
| c********t
发帖数: 5706 | 3 看来是。还是学习用stack的方法吧。 多谢！
【在 l*******b 的大作中提到】
: 递归太深，stack 爆了？
:
: +1
|
|
