Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Largest Rectangle in a Histogram by lukasz.bogaczynski
def largest_histogram(histogram):
bars_history = []
bar_index = 0
area = 0
while bar_index <= len(histogram):
if len(bars_history) < 1 or (bar_index < len(histogram) and histogram[bar_index] > histogram[bars_history[-1]]):
bars_history.append(bar_index)
bar_index = bar_index + 1
continue
last_bar_index = bars_history.pop()
if len(bars_history) < 1:
area = max(area, histogram[last_bar_index] * bar_index)
else:
area = max(area, histogram[last_bar_index] * (bar_index - bars_history[-1] - 1))
return area
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!")
Nov. 7, 2017