Given an array of bar heights representing a histogram, find the largest rectangle that can be formed.
With [2, 1, 5, 6, 2, 3]:
- A rectangle of height
5spanning bars 2-3 has area5 × 2 = 10. - A rectangle of height
2spanning bars 0-5 has area2 × 6 = 12. But bar 1 is only height 1, so this doesn't work. - The largest is
10(bars 2-3 with height 5).
For each bar, imagine extending it left and right as far as possible while maintaining at least that height.
Constraints: bars .