Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Find groups that stick up above minimum height solution in Clear category for Largest Rectangle in a Histogram by rossras
from itertools import groupby
def largest_histogram(histogram):
# Look for a rectangle all the way across the bottom, or for groups that
# stick up above the minimum height
def is_tall(x):
return x > min_height
result = 0
stack = [histogram]
while stack:
group = stack.pop()
min_height = min(group)
result = max(result, min_height*len(group))
new_groups = [list(g) for k, g in groupby(group, key=is_tall) if k]
# Only put a group back on the stack if it's big enough to bother with
stack.extend(g for g in new_groups if sum(g) > result)
return result
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!")
Aug. 9, 2018