Data Structures19 sections · 729 units
Open in Course

Histogram - The Approach

When to calculate

Use a monotonic increasing stack (smallest on bottom). Store indices. When you encounter a bar shorter than the stack top, the top bar can't extend further right.

Pop it and calculate its area. The left boundary is the new stack top (or 1-1 if empty). The right boundary is the current index minus one.

After processing all bars, pop remaining elements. Their right boundary is nn (they extend to the end).