<s> """<STR_LIT>""" <EOL> import sys <EOL> __author__ = '<STR_LIT>' <EOL> class Solution : <EOL> def largestRectangleArea ( self , height ) : <EOL> """<STR_LIT>""" <EOL> if not height : <EOL> return <NUM_LIT:0> <EOL> n = len ( height ) <EOL> gmax = - sys . maxint - <NUM_LIT:1> <EOL> inc_stack = [ ] <EOL> for i in xrange ( n ) : <EOL> while inc_stack and height [ inc_stack [ - <NUM_LIT:1> ] ] > height [ i ] : <EOL> last = inc_stack . pop ( ) <EOL> if inc_stack : <EOL> area = height [ last ] * ( i - ( inc_stack [ - <NUM_LIT:1> ] + <NUM_LIT:1> ) ) <EOL> else : <EOL> area = height [ last ] * i <EOL> gmax = max ( gmax , area ) <EOL> inc_stack . append ( i ) <EOL> i = n <EOL> while inc_stack : <EOL> last = inc_stack . pop ( ) <EOL> if inc_stack : <EOL> area = height [ last ] * ( i - ( inc_stack [ - <NUM_LIT:1> ] + <NUM_LIT:1> ) ) <EOL> else : <EOL> area = height [ last ] * i <EOL> gmax = max ( gmax , area ) <EOL> return gmax <EOL> def largestRectangleArea_TLE ( self , height ) : <EOL> """<STR_LIT>""" <EOL> if not height : <EOL> return <NUM_LIT:0> <EOL> max_area = - <NUM_LIT:1> << <NUM_LIT:32> <EOL> for ind , val in enumerate ( height ) : <EOL> min_h = val <EOL> max_area = max ( max_area , val * <NUM_LIT:1> ) <EOL> for j in xrange ( ind , - <NUM_LIT:1> , - <NUM_LIT:1> ) : <EOL> min_h = min ( min_h , height [ j ] ) <EOL> current_area = min_h * ( ind - j + <NUM_LIT:1> ) <EOL> max_area = max ( max_area , current_area ) <EOL> return max_area <EOL> def largestRectangleArea_complex ( self , height ) : <EOL> """<STR_LIT>""" <EOL> if not height : <EOL> return <NUM_LIT:0> <EOL> global_max = - <NUM_LIT:1> << <NUM_LIT:32> <EOL> for ind , val in enumerate ( height ) : <EOL> if ind + <NUM_LIT:1> < len ( height ) and val <= height [ ind + <NUM_LIT:1> ] : <EOL> continue <EOL> min_h = val <EOL> global_max = max ( global_max , min_h * <NUM_LIT:1> ) <EOL> for j in xrange ( ind , - <NUM_LIT:1> , - <NUM_LIT:1> ) : <EOL> min_h = min ( min_h , height [ j ] ) <EOL> current_area = min_h * ( ind - j + <NUM_LIT:1> ) <EOL> global_max = max ( global_max , current_area ) <EOL> return global_max <EOL> def largestRectangleArea_error ( self , height ) : <EOL> """<STR_LIT>""" <EOL> if not height : <EOL> return <NUM_LIT:0> <EOL> length = len ( height ) <EOL> global_max = - <NUM_LIT:1> << <NUM_LIT:32> <EOL> inc_stack = [ ] <EOL> i = <NUM_LIT:0> <EOL> while i < length : <EOL> if not inc_stack or height [ i ] >= height [ inc_stack [ - <NUM_LIT:1> ] ] : <EOL> inc_stack . append ( i ) <EOL> i += <NUM_LIT:1> <EOL> else : <EOL> last = inc_stack . pop ( ) <EOL> if inc_stack : <EOL> area = height [ last ] * ( i - last ) <EOL> else : <EOL> area = height [ last ] * i <EOL> global_max = max ( global_max , area ) <EOL> while inc_stack : <EOL> last = inc_stack . pop ( ) <EOL> if inc_stack : <EOL> area = height [ last ] * ( i - last ) <EOL> else : <EOL> area = height [ last ] * i <EOL> global_max = max ( global_max , area ) <EOL> return global_max <EOL> if __name__ == "<STR_LIT:__main__>" : <EOL> height = [ <NUM_LIT:4> , <NUM_LIT:2> , <NUM_LIT:0> , <NUM_LIT:3> , <NUM_LIT:2> , <NUM_LIT:5> ] <EOL> assert Solution ( ) . largestRectangleArea ( height ) == Solution ( ) . largestRectangleArea_complex ( height ) </s>
