Maximum of Every Window

A window that covers k numbers in a row slides along nums one step at a time, from the left end to the right end. Write window_max(nums, k) that returns a list of the largest number in the window at each of its positions, from left to right. There are len(nums) - k + 1 positions.

Examples

window_max([4, 2, 12, 3, 8, 1, 7], 3)   # returns [12, 12, 12, 8, 8]
window_max([5, 4, 3, 2, 1], 2)          # returns [5, 4, 3, 2]
window_max([9, 1, 6], 1)                # returns [9, 1, 6]

The windows of the first example are [4, 2, 12], [2, 12, 3], [12, 3, 8], [3, 8, 1] and [8, 1, 7].

Constraints

• 1 <= k <= len(nums) <= 100,000
• -10^4 <= nums[i] <= 10^4

Note

Taking max() of every window costs k steps per window. Aim for a total number of steps that grows with len(nums) alone, whatever k is.