Monotonic Stack Deep Dive

Concepts: pyMonotonicIncreasing, pyMonotonicDecreasing, pyHistogram

A monotonic stack is a stack that maintains a sorted invariant. Monotonic increasing: values from bottom to top are non-decreasing. Monotonic decreasing: values from bottom to top are non-increasing. The invariant is maintained by popping elements that would violate it when a new element arrives. Those pops are where the problem's answers get recorded. This pattern appears in two critical interview problems: largest rectangle in histogram and daily temperatures. Monotonic Increasing vs Decreasing Largest Rectangle in Histogram This is the hardest classic monotonic stack problem. It appears at Google, Meta, and Databricks. Given an array of bar heights, find the largest rectangle that fits entirely within the histogram. For each bar, the rectangle it anchors has width determined by how far