Answer to Question #280301 in Python for kaavya

Question

Area of Largest Rectangle in Histogram:

Given a list of integer heights representing the histograms bar height where the width of each bar is 1, return the area of largest rectangle in the histogram.

Input: The input will be a single line containing space-separated integers, denoting the heights of the bars.

Output: The output should be a single line containing the area of the largest rectangle in the rectangle.

Sample Input 1:

2 1 5 6 2 3

Sample Output 1:

10

Sample Input 2:

65 87 96 31 32 86 57 69 20 42

Sample Output 2:

248

Answer 1

def ​maximumArea(histogram):
   ​stack = list()

   ​max_area = 0
   ​index = 0
   ​while index < len(histogram):

       ​if (not stack) or (histogram[stack[-1]] <= histogram[index]):
           ​stack.append(index)
           ​index += 1
       ​else:

           ​top_of_stack = stack.pop()

           ​area = (histogram[top_of_stack] *
                   ​((index - stack[-1] - 1)
                    ​if stack else index))

           ​max_area = max(max_area, area)

   ​while stack:

       ​top_of_stack = stack.pop()
       ​area = (histogram[top_of_stack] *
               ​((index - stack[-1] - 1)
                ​if stack else index))

       ​max_area = max(max_area, area)

   ​return max_area


if ​__name__ == '__main__':
   ​histo = [65,87,96,31,32,86,57,69,20,42]
   ​print("Maximum area:", maximumArea(histo))