Answer to Question #217921 in Python for srikanth

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 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))