The maximum in every sliding window

A performance overlay showing the worst frame time in the last sixty frames, or a chart drawing a rolling peak, needs the maximum of a window that moves one step at a time. Recomputing the maximum for each window is O(n * k); a monotonic deque does the whole sweep in one pass.

Implement maxSlidingWindow(nums, k). nums is an array of numbers and k is the window size. Return an array holding the largest number in each window of k consecutive values, starting with the window at index 0 and moving one step right at a time, so the result has nums.length - k + 1 entries. Return an empty array when nums is empty, when k is less than 1, or when k is larger than the array.

What it has to do

• Return one maximum per window, left to right.
• Return an empty array when k is larger than the input, when k is below 1, or when the input is empty.
• Handle negative numbers and repeated values.
• Handle k equal to 1 and k equal to the array length.
• Make a single pass rather than scanning each window.

Your workspace