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 DP into . By the end, you'll recognize sliding window patterns in DP and implement monotonic queue optimizations. We'll solve four classic problems together.