Stretch Problem: Largest Rectangle in a Histogram (hard)

This problem is optional and it is hard. Nothing later in the course depends on it. It is the hardest stack question in this course, and the technique it teaches, a stack kept in increasing order, is the one behind Next Greater Element earlier in the chapter.

Problem Statement

You are given an array heights where heights[i] is the height of a bar of width 1 in a histogram. The bars stand side by side.

Return the area of the largest rectangle that fits inside the histogram. A rectangle may span several bars, and its height is then limited by the shortest bar it covers.