Sliding Window Maximum

Given an integer array nums and a window size k, return a list of the maximum values in each sliding window of size k as the window moves from left to right.

Function signature

func MaxSlidingWindow(nums []int, k int) []int

Examples

Example 1:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]

Example 2:

Input: nums = [2,1], k = 1
Output: [2,1]

Constraints

• 1 <= nums.length <= 10^5
• 1 <= k <= nums.length
• -10^4 <= nums[i] <= 10^4

Hints

1. A monotonic deque keeps indices in decreasing order of values.
2. The front of the deque is always the max for the current window.
3. Remove indices that fall out of the window.

Notes

• O(n log n) with a heap works, but O(n) is possible with a deque.
• Store indices, not values, to know when they expire.