Monotonic Stack

"For each element in the array, find the next greater element" is a brute-force `O(n^2)` problem until you notice that a stack maintained in decreasing order lets you answer every query as a side effect of a single left-to-right scan. The whole algorithm runs in `O(n)`, and the same monotonic-stack pattern solves trapping rain water, largest rectangle in a histogram, stock spans, and a long tail of related problems with the same template. **Advanced Greedy & Data Structures** is where greedy thinking meets specialized scaffolding. You will implement the monotonic stack pattern for next-greater and next-smaller variants, the monotonic deque for sliding-window maximum and minimum (also a key DP optimization), and sweep-line algorithms for interval and event problems (meeting rooms, interval merge, rectangle area union). The lesson closes with advanced greedy problems that need a heap or priority queue: full Huffman encoding, task scheduling with cooldown, the gas station problem, and activity selection with deadlines and profits. In **Greedy (Intro)**, you saw simple greedy strategies that needed only sorting. **Heaps & Priority Queue** taught you `O(log n)` access to the minimum or maximum, which is exactly what these advanced greedy patterns rely on for their efficiency. Next, **Branch and Bound** extends backtracking with the same kind of bounding-function pruning, applied to optimization search trees.