##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
Find maximum in each window of size k.
Problem: Return the maximum in each sliding window of size k.
Naive: O(nk). Optimal: Monotonic deque storing indices in decreasing value order.
For each element: remove out-of-window indices from front, remove smaller elements from back (they can never be max), add current index. Front always holds max.
Time: O(n). Space: O(k).
See the implementation unit for code.
