Monotonic Deque: The Separator Between Good and Great

Concepts: pyMonotonicDeque, pySlidingWindowMax

Here's the thing about sliding window maximum: when I ask this question, I'm not actually testing whether you know the answer. I'm testing your debugging instinct when I tell you your first approach is too slow. Almost everyone starts with 'maintain a sorted structure and query the max.' The question is whether you know WHY a deque beats a heap here, and whether you can reconstruct the invariant from first principles. Let me walk you through how to think about this from scratch. The Core Insight: Useless Elements Suppose your window currently contains [3, 1, 5, 2] and K=4. The element 5 will be the maximum for every future window that contains it. Elements 3 and 1, which are to the LEFT of 5 and SMALLER than 5, can never be the maximum. They are useless. They will leave the window before 5