The monotonic stack is the O(n) trick for finding the next greater or smaller element — a sorted stack you maintain on the fly, with one deceptively simple pop-while loop at its core. Used in Daily Temperatures, Largest Rectangle in Histogram, and Trapping Rain Water.
#monotonic-stack#stack#arrays
12 min