Basically, you need to quickly lookup to the left, what is the closest column whose height is smaller than you (so a rectangle with h=your height can not extend beyond that column). This is done using a stack maintaining non-decreasing order, with indices stored. Also, you should look right. But how to do it in just O(n)? because when you pop stuff in the stack, you are actually exactly finding the closest smaller column in the right direction. It is this column that forces you to be poped out of the stack (due to the non-decreasing order), and you can only be poped out once. so it must be the first one in the right direction that force you to do so.
Anyway, you can record ever such rect and find max of them as follows:
class Solution: # @param height, a list of integer # @return an integer def largestRectangleArea(self, height): if not height: return 0 # using a queue to keep track of left, closest element smaller than current one; and right smallest element smaller than a given one (that is when it is poped out). and save max in each iteration stack= maxrect=0 for i in range(len(height)): current=height[i] while stack: if stack[-1]>current: (index,h,left)=stack.pop() maxrect=max(h*(i-index-1)+left,maxrect) elif stack[-1]==current: stack.pop() else: break if stack: stack.append((i,current,current*(i-(stack[-1])))) else: stack.append((i,current,current*(i+1))) while stack: (index,h,left)=stack.pop() maxrect=max(h*(len(height)-index-1)+left,maxrect) return maxrect