max area of rectangle.

Look at the picture below which pretty much shows the cases you need to consider.

Think of the heights in terms of number of increasing and decreasing values

1 3 6 8 7 2 4 1

For each rectangle, traverse each index from left to right and calculate the maximum available only when the height goes down. Compute the maximum of all sub calculations. When the next building is taller than the previous, add it to the stack (to be processed later).

Also notice that we need to extend building 5 backthrough building 4.

How do you know to stop at building 4? Easy, the next active area (coming from building 3) has a height lower than building 5's, so that area is still active (in other words it will go through building 5).

When the next building is shorter: pop off stack until you find a starting area with a smaller height (than the current building) or you empty the stack (meaning it goes all the way back through the first building).

Now push this building's height along with it's left position onto the stack. 

When you pop off the stack, this means you've found the right side of an area, so compute its area and see if it's the maximum.

Also when you find the "left wall" for the current building (meaning you found a smaller building in the stack or went all the way back to the first building), you need to remember that position in addition to the height of the current building so that when the current building is eventually popped off of the stack, you can properly compute it's area.

Notice how building 6 extends both backwards and forwards, such that when I get to building 8, I have to know that building 6's height extended all the way back through building 2.