Given an array nums and sliding window size k, return the maximum value in each window as the window slides from left to right.
nums = [1,3,-1,-3,5,3,6,7], k = 3
# Window [1,3,-1] → max 3
# Window [3,-1,-3] → max 3
# Window [-1,-3,5] → max 5
# Window [-3,5,3] → max 5
# Window [5,3,6] → max 6
# Window [3,6,7] → max 7
# Output: [3,3,5,5,6,7]
Use a monotonic decreasing deque. The deque stores indices, and the front always has the maximum of the current window.
Time: O(n) because each element is added and removed from the deque at most once.
📋 Instructions
Implement `max_sliding_window(nums, k)` using a deque.
Test with `nums = [1,3,-1,-3,5,3,6,7]`, `k = 3`.
Print the result.
Use collections.deque. For each element: (1) Remove front if it's outside the window. (2) Remove elements from back while they're smaller than current. (3) Add current index. (4) Once i >= k-1, append deque[0] element to result.