#171MediumQueues· Monotonic Deque

Peak Load in Every Window

A monitoring dashboard records the CPU load of a server once per second. To show how spiky the last stretch of time was, it displays the **highest load in the most recent `w` readings** and updates that figure every second. Given the full list of readings `loads` and the window size `w`, return the maximum of every window of `w` consecutive readings, from the first window to the last. The list has `n - w + 1` windows for `n` readings.

Input format

`loads`: an array of integers; `w`: the window size.

Output format

An array of `n - w + 1` integers: the maximum of each window, left to right.

Examples

Input: loads = [1, 3, -1, -3, 5, 3, 6, 7], w = 3

Output: [3, 3, 5, 5, 6, 7]

The windows are [1,3,-1], [3,-1,-3], [-1,-3,5], [-3,5,3], [5,3,6] and [3,6,7], with maxima 3, 3, 5, 5, 6, 7.

Input: loads = [9], w = 1

Output: [9]

A single reading is its own window.

Input: loads = [4, 2, 12, 3], w = 4

Output: [12]

One window covers everything and its maximum is 12.

Constraints

1 <= loads.length <= 10^5
-10^4 <= loads[i] <= 10^4
1 <= w <= loads.length

#deque
#sliding-window
#monotonic-queue