国内很多人买iphone 5s实际上是因为它便宜# PDA - 掌中宝
c*t
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);
}
}
}
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);
}
}
}
