Largest Rectangle Under Histogram
Given an array of non-negative integers representing the heights of bars in a histogram where the width of each bar is 1, find the area of the largest rectangle that can be formed within the histogram. The rectangle must be axis-aligned and have its sides parallel to the coordinate axes.
Input
The first line contains an integer N, the number of bars in the histogram. The second line contains N space-separated non-negative integers representing the heights of the bars.
Output
Print a single integer, the maximum area of a rectangle that can be formed under the histogram.
Constraints
1 <= N <= 200000, 0 <= heights[i] <= 10^9
Example 1
5 2 1 5 6 2 3
10
The largest rectangle has height 5 and width 2 (bars 5 and 6), giving an area of 10. Another rectangle has height 2 and width 4 (bars 1, 5, 6, 2), area 8.
Example 2
3 7 2 8
8
The largest rectangle has height 2 and width 3, area 6. Other rectangles: height 7, width 1, area 7; height 8, width 1, area 8. Max area is 8.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 2 1 5 6 2 3
3 7 2 8