84-Largest-Rectangle-in-Histogram

1. Largest Rectangle in Histogram

• 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.

          6 
        5 _
        _| |
       | | |  3
    2  | | |2 _
    _ 1| | |_| |
   | |_| | | | |
   |_|_|_|_|_|_|
   Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].
          6 
        5 _
        _| |
       |/|/|  3
    2  |/|/|2 _
    _ 1|/|/|_| |
   | |_|/|/| | |
   |_|_|/|/|_|_|
   The largest rectangle is shown in the shaded area, which has area = 10 unit.
- Example:
  Input: [2,1,5,6,2,3]
  Output: 10