Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
O(n) solution in Speedy category for Largest Rectangle in a Histogram by Sim0000
def largest_histogram(hist):
stack = []
max_area = 0
i = 0;
while i < len(hist):
if not stack or hist[i] >= hist[stack[-1]]:
stack.append(i)
i += 1
else:
p = stack.pop()
max_area = max(max_area, hist[p] * (i - stack[-1] - 1 if stack else i))
while stack:
p = stack.pop()
max_area = max(max_area, hist[p] * (i - stack[-1] - 1 if stack else i))
return max_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. 22, 2016
Comments:
