All problems

Sliding Window Maximum

Hard · sliding window

A sensor records a reading every second, and the list nums holds those readings in order. You look at them through a frame that is k readings wide. The frame starts at the very beginning of the list, and then moves one reading to the right at a time until it reaches the end, so at each position it shows exactly k neighbouring readings.

For every position of the frame, take the largest reading it shows. Return these largest values as a list, in the order the frame visited them (from the left end of nums to the right end).

The returned list has len(nums) - k + 1 values. Readings may repeat and may be negative.

Examples

Example 1

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

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

The frames show [1, 3, -1], [3, -1, -3], [-1, -3, 5], [-3, 5, 3], [5, 3, 6] and [3, 6, 7].

Example 2

Input: nums = [4, 2, 12, 3], k = 2

Output: [4, 12, 12]

The frames show [4, 2], [2, 12] and [12, 3].

Example 3

Input: nums = [8], k = 1

Output: [8]

One reading and a frame of width 1.

Constraints