Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
using a dict to store rectangles (key=high, value=length) solution in Clear category for Largest Rectangle in a Histogram by a_ntv
def largest_histogram(histogram):
maxarea=0
rects={0:0}
for x in histogram:
for i in range(1,x+1):
rects[i]=rects.get(i,0)+1
for i in range(x+1,max(rects)+1):
rects[i]=0
maxarea=max(maxarea,*map(lambda a:a[0]*a[1],rects.items()))
return maxarea
if __name__ == "__main__":
#These "asserts" using only for self-checking and not necessary for auto-testing
assert largest_histogram([5]) == 5, "one is always the biggest"
assert largest_histogram([5, 3]) == 6, "two are smallest X 2"
assert largest_histogram([1, 1, 4, 1]) == 4, "vertical"
assert largest_histogram([1, 1, 3, 1]) == 4, "horizontal"
assert largest_histogram([2, 1, 4, 5, 1, 3, 3]) == 8, "complex"
print("Done! Go check it!")
Feb. 17, 2020
