Hints — p95 Sliding Window Maximum

1. Brute is O(n·k); target O(n).

2. Monotonic decreasing deque of indices. Deque values (in nums) strictly decreasing from front to back. Front is always the current window’s max.

3. For each i: (a) pop from BACK while nums[back] <= nums[i] (they can never be max again); (b) push i; (c) pop from FRONT if front <= i - k (out of window); (d) if i >= k - 1, record nums[deque[0]].

4. Why O(n)? Each index pushed once and popped at most once → 2n total deque operations.

5. Alternative: max-heap with lazy deletion. Push (-v, i). Before reading top, pop while top’s index is out of window. O(n log n).

If stuck: see solution.py.