Largest Rectangle in Histogram
Hard · Stack & Monotonic Stack · about 30 minutes
Asked at Google, Amazon, Microsoft, Uber.
heights describes a bar chart whose bars are all 1 unit wide and stand next to each other. Among all axis-aligned rectangles that lie completely inside the bars, find the one with the biggest area and return that area.