Answer to Question #188390 in Python for karthik

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

#define area to return the maximum area in a histogram
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))