Examples of the enumeration method for finding the maximum rectangular area in a histogram
- 2021-06-28 12:47:31
- OfStack
Find the maximum rectangular area in the histogram:
For example, given histogram {2,3,1,2,4,2}
Then the maximum rectangular area in the histogram is x=(3,6), |x|=3, y=2, max area=6
Think: Using Enumeration
/* Enumeration forward of current position */
publicclass Solution{
static int histogramMaxArea( int[]a ){
int maxS =a [0];
for(int i =0;i <a .length;i ++){ // Enumerate backwards in order in the histogram
int min =a [i ]; // Record current bar and previous minimum
int m =0; // Record bottom edge length
for(int j =i ;j >=0;j --){ // Take the largest rectangle forward in turn
m++;
if( a[ j]< min){
min= a[ j];
}
int s =m *min ; // Rectangular Area Calculation
if( s> maxS){
maxS= s;
}
}
}
return maxS ;
}
public static void main(String args[]){
int a []={2,1,1,2};
int maxArea =histogramMaxArea( a);
System. out.print(maxArea );
}
}
summary