Monotonic Stack

Opening scenario

Largest Rectangle in Histogram (LC 84): given nonnegative bar heights heights[i] (width 1 each), return the area of the largest rectangle that fits entirely under the skyline. Follow-up you should expect: Maximum Binary Tree (LC 654) — given a nonempty array of distinct values, build a tree where the root is the array max, its left subtree is built from the left subarray, and its right subtree from the right subarray.

LC numbers identify LeetCode problems.

For each bar, imagine a rectangle with that bar's height. Which bars stop it from extending left or right, and when can a left-to-right scan determine those limits?

Question progression

Q1 — For each bar, what do you actually need to know to compute its rectangle?

Question: A rectangle of height heights[i] extends left and right until it hits a shorter bar. So for each i you need the nearest shorter bar to the left and to the right. Brute force scans outward from every bar. What does that…