def largest_rectangle(height):
n = len(height)
if n < 2:
return height[0] if n else 0
height.append(0)
max_area = 0
for i in range(0, n + 1):
j = i  1
while j >= 0 and height[j] > height[i]:
max_area = max(max_area, height[j] * (i  j))
height[j] = height[i]
j = 1
return max_area
91 ms python solution with constant space

As "commented" said it is not true constant space
I modified code a bit to make it really constant space.. And I think it will be easier to read and understand.
Basically when a height drop detected, the code searches potential largest area that will not be seen as the algorithm goes on running.
BTW I think this is a greedy algorithm
def largestRectangleArea(self, height): if not height: return 0 lens = len(height) height.append(0) # gurad maxArea = 0 for r in range(0,lens): if height[r] > height[r+1]: l = r minInrange = height[r] while height[l] > height[r+1] and l >= 0: minInrange = min(minInrange, height[l]) maxArea = max(maxArea, minInrange*(rl+1)) l = 1 return maxArea