Largest rectangle histogram - mock interview

Largest rectangle histogram - mock interview

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1,
  find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given heights = [2,1,5,6,2,3],
return 10.

Julia drawed the diagram to show the rectangle histogram: 
              ____
          ____
  
                      _____
  ____            ____
      ____
  ______________________________________________
  0   1   2   3   4   5    6
                  |
The interviewee wrote the following: 

First the interviewee gave the brute force analysis:
For each bar:
Expand until left and right are less than height[i]
maxHeight = max(maxHeight, height * (right - left - 1))
O(N^2)

And then he gave the optimal solution using stack. 

Stack: (added after mock interview by Julia, first value is index, second value is height) 
  (-1,0) (1,1) (4,2)

Rectangle: (added by Julia)
right  =  6
height =  1
left   = -1

area = height * (right - left - 1) = 6 * 1
max = 10