Section Recap

You now understand stacks at a deep level:

$1.$ Basic stacks: LIFO structure for matching, nesting, and reversal problems. $O(1)$ operations.

$2.$ Monotonic decreasing stacks: find next/previous greater element in $O(n)$.

$3.$ Monotonic increasing stacks: find next/previous smaller element in $O(n)$.

$4.$ The histogram pattern: when popping, you know both left and right boundaries. Stacks are simple but effective. The monotonic variant is one of the most useful techniques in competitive programming. Practice until the pattern becomes automatic. In the next section, I'll show you queues and their monotonic variant for sliding window problems.