Largest rectangle in histogram

The best rectangle as tall as a bar stretches until it meets a smaller bar on each side. One stack pass finds the closest smaller bar on the left and on the right of every bar; then each bar's area is its height times the width between them.

On the stack bar heights increase from bottom to top; the index under each is its bar.