You are given an array of integers where each element represents the height of a bar in a histogram. The bars are placed in the exact same sequence as given in the array. You need to find the area of the largest rectangle found in the histogram.

Problem Note

  • The width of each bar is 1.
  • You cannot change the sequence of bars.

Example 1:

Input: [2,1,5,6,2,3]
Output: 10
              6
             ___
          5 |   |
         ___|   |
        |   |   |
        |   |   |
        |   |   |     3
        |   |   |    ___
  2     |   |   | 2 |   |
 ___    |   |   |___|   |
|   | 1 |   |   |   |   |
|   |___|   |   |   |   |
|   |   |   |   |   |   |
|   |   |   |   |   |   |
-------------------------


Explanation: 
              6
             ___
          5 |   |
         ___|___|
        |***|***|
        |***|***|
        |***|***|     3
        |***|***|    ___
  2     |***|***| 2 |   |
 ___    |***|***|___|   |
|   | 1 |***|***|   |   |
|   |___|***|***|   |   |
|   |   |***|***|   |   |
|   |   |***|***|   |   |
-------------------------