Answer to Question #186374 in Python for phani

Question

Area of Largest Rectangle in Histogram

Given an list of integer 

heights representing the histogram's bar height where the width of each bar is 1, return the area of the 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.

Explanation

For example, if the given list of numbers are 

2 1 5 6 2 3 , when they are drawn adjacent to each other according to their heights, the histogram will be like

The largest rectangle can be found in between 5 and 6, which is 10.

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 GetMaxArea_Hist(BarVal):
    temp = list()
    MaxArea = 0
    ind = 0
    while ind < len(BarVal):
        if (not temp) or (BarVal[temp[-1]] <= BarVal[ind]):
            temp.append(ind)
            ind += 1
        else:
            t = temp.pop()
            Area = (BarVal[t] * 
                   ((ind - temp[-1] - 1) 
                   if temp else ind))
            MaxArea = max(MaxArea, Area)
    while temp:
        t = temp.pop()
        area = (BarVal[t] * 
              ((ind - temp[-1] - 1) 
                if temp else ind))
        MaxArea = max(MaxArea, Area)
    return MaxArea




InputArray = [2,1,5,6,2,3]
MaxArea = GetMaxArea_Hist(InputArray)
print("\nInput: ",InputArray)
print("Maximum area is ",MaxArea) 


InputArray = [65, 87, 96, 31, 32, 86, 57, 69, 20, 42]
MaxArea = GetMaxArea_Hist(InputArray)
print("\nInput: ",InputArray)
print("Maximum area is ",MaxArea)