hardQueues and dequesSliding window target 40 min
Sliding window maximum
You get a list of integers nums and a window size k. A window is k neighboring items. Start with the window over the first k items, then slide it right one position at a time until it covers the last k items. Return a list with the largest number in each window, from left to right.
There are len(nums) - k + 1 windows, so the answer has that many numbers.
Example 1
Input
nums = [2, 5, 1, 4, 3, 1, 6], k = 3Output[5, 5, 4, 4, 6]The windows are [2, 5, 1], [5, 1, 4], [1, 4, 3], [4, 3, 1] and [3, 1, 6].
Example 2
Input
nums = [9, 7, 5, 3], k = 2Output[9, 7, 5]The numbers fall, so each window's largest is its first item, and that item leaves on the next slide.
Example 3
Input
nums = [-4, 8, -1], k = 1Output[-4, 8, -1]A window of one item is its own largest number.
Constraints
1 ≤ k ≤ len(nums) ≤ 105
-105 ≤ nums[i] ≤ 105
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.
Run examples checks the examples. Submit runs every test, including edge cases and, when the problem has one, a speed check on a large input.