Largest Rectangular Area in a Histogram | Set 2 | Java program to find maximum rectangular area in linear time ; The main function to find the maximum rectangular area under given histogram with n bars ; Create an empty stack . The stack holds indexes of hist [ ] array The bars stored in stack are always in increasing order of their heights . ; Initialize max area ; To store top of stack ; To store area with top bar as the smallest bar ; Run through all bars of given histogram ; If this bar is higher than the bar on top stack , push it to stack ; If this bar is lower than top of stack , then calculate area of rectangle with stack top as the smallest ( or minimum height ) bar . ' i ' is ' right ▁ index ' for the top and element before top in stack is ' left ▁ index ' ; store the top index ; pop the top ; Calculate the area with hist [ tp ] stack as smallest bar ; update max area , if needed ; Now pop the remaining bars from stack and calculate area with every popped bar as the smallest bar ; Driver program to test above function
import java . util . Stack ; public class RectArea { static int getMaxArea ( int hist [ ] , int n ) { Stack < Integer > s = new Stack < > ( ) ; int max_area = 0 ; int tp ; int area_with_top ; int i = 0 ; while ( i < n ) { if ( s . empty ( ) || hist [ s . peek ( ) ] <= hist [ i ] ) s . push ( i ++ ) ; else { tp = s . peek ( ) ; s . pop ( ) ; area_with_top = hist [ tp ] * ( s . empty ( ) ? i : i - s . peek ( ) - 1 ) ; if ( max_area < area_with_top ) max_area = area_with_top ; } } while ( s . empty ( ) == false ) { tp = s . peek ( ) ; s . pop ( ) ; area_with_top = hist [ tp ] * ( s . empty ( ) ? i : i - s . peek ( ) - 1 ) ; if ( max_area < area_with_top ) max_area = area_with_top ; } return max_area ; } public static void main ( String [ ] args ) { int hist [ ] = { 6 , 2 , 5 , 4 , 5 , 1 , 6 } ; System . out . println ( " Maximum ▁ area ▁ is ▁ " + getMaxArea ( hist , hist . length ) ) ; } }