我来抛砖吧。
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) );
}
}
