def largest_rectangle(height): n = len(height) if n < 2: return height 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
It's concise and like a magic, but I cannot understand the algorithm in your code.
Why you use 'height[j] = height[i]'
Could you please explain it?
I would appreciate if you can explain all.
In i th iteration, height[j] = height[i] for all j >= 0 and height[j] > height[i] effectively makes height[:i] non decreasing, which is equivalent to using a stack that stores the indices of elements that are in non decreasing order.
In my opinion, this can't be considered as constant space because you reused the input 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*(r-l+1)) l -= 1 return maxArea
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.