class Solution: # @param height, a list of integer # @return an integer def largestRectangleArea(self, height): # Add last height as 0 to make the last part works for stack height.append( 0 ) stack =  i = 0 maxArea = 0 while i < len(height): if stack== or height[ stack[-1] ] <= height[i]: stack.append( i ) i = i+1 else: num = stack.pop() if stack!=: area = height[num] * (i - stack[-1] -1) else: area = height[num] * (i) maxArea = max(maxArea, area)
Step 1: Traverse all possible large rectangles
Since we need to find the largest rectangle, we need to traversal all possible rectangles and to compare each of the area. But...all possible? There seems to be lots of combinations.
Actually not!! Because we are only interested in the largest. So for the following example we do not need to consider the blue rectangle. We only need to consider the red one: Why?
Step 2: Find the nearest smaller value of each bar
Go back again to the example, the largest private rectangle is the red one not the blue one? Why because for the blue one there's one more bar D which is higher than B. So finding the largest private rectangle is the problem of finding the nearest smaller value. This is actually a classic algorithm problem, which can be find in All Nearest Smaller Values
The most ideal way to find the nearest smaller value is using stack structure.While traversing the histogram, we push the bar which is higher than the bar at the top of the stack. Therefore, we maintain an ascending stack. In the above example, we have [A, B, C, D] inside stack in ascending order.
When we reach E, which is shorter than D( stack top ), we pop D. Now, we know for sure D's nearest smaller one is E and C. Similarly, we pop can find the nearest smaller one in B,C as well. Later we push E back to the stack. Now the stack is [A, E], which is still in ascending order. We can find their nearest smaller bar by the same logic.
S = new empty stack data structure for x in the input sequence: while S is nonempty and the top element of S is greater than or equal to x: pop S if S is empty: x has no preceding smaller value else: the nearest smaller value to x is the top element of S push x onto S