Largest Rectangular Area in a Histogram | Set 2 | C # 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 Code
using System ; using System . Collections . Generic ; class GFG { public static int getMaxArea ( int [ ] hist , int n ) { Stack < int > s = new Stack < int > ( ) ; int max_area = 0 ; int tp ; int area_with_top ; int i = 0 ; while ( i < n ) { if ( s . Count == 0 || hist [ s . Peek ( ) ] <= hist [ i ] ) { s . Push ( i ++ ) ; } else { tp = s . Peek ( ) ; s . Pop ( ) ; area_with_top = hist [ tp ] * ( s . Count == 0 ? i : i - s . Peek ( ) - 1 ) ; if ( max_area < area_with_top ) { max_area = area_with_top ; } } } while ( s . Count > 0 ) { tp = s . Peek ( ) ; s . Pop ( ) ; area_with_top = hist [ tp ] * ( s . Count == 0 ? 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 = new int [ ] { 6 , 2 , 5 , 4 , 5 , 1 , 6 } ; Console . WriteLine ( " Maximum ▁ area ▁ is ▁ " + getMaxArea ( hist , hist . Length ) ) ; } }