Histogram Reordering

If we sort the histograms by their height, this ordering will definitely have the highest possible rectangle, but this ordering might not be the lexicographically smallest one. But using this ordering we can find the maximum area possible.

Now there might be several ways of generating the maximum area. For example, if the maximum area is 12, then there are 6 ways to generate that area,

1. 12 histograms of height 1
2. 6 histograms of height 2
3. 4 histograms of height 3
4. 3 histograms of height 4
5. 2 histograms of height 6
6. 1 histogram of height 12

For each such combination, we will generate the lexicographically smallest ordering and finally lexicographically smallest of them all is the answer.

Time Complexity: $O(n*log(n))$

Space Complexity: $O(n)$