Intro

You know how to improve DP (dynamic programming) with Convex Hull Trick when transitions involve line queries. But what if your DP needs the minimum or maximum over a sliding window of previous states? I'll show you monotonic queues.

This data structure keeps candidates in sorted order while elements enter and leave a window. You'll use it to turn $O(nk)$ DP into $O(n)$. By the end, you'll recognize sliding window patterns in DP and implement monotonic queue optimizations. We'll solve four classic problems together.