Maximum of Each Window
You get an integer array nums and an integer k.
A window of size k starts at the left end of nums and moves one step to the right at a time, until its right edge reaches the last element. So there are nums.length - k + 1 windows.
Return an array with the largest value of each window, in order from the leftmost window to the rightmost window.
Hint
Finding the largest value of every window from scratch costs O(n·k). Instead, keep a double-ended queue (deque) of indices whose values go down from front to back. When a new value comes in, remove smaller values from the back, because they can never be a window's largest value again. Remove the front index when it leaves the window. The front is then always the largest value of the current window. This is O(n).
Examples
Example 1
- Input:
- [2,7,3,-1,4,1,6], 3
- Output:
- [7,7,4,4,6]
The windows are [2,7,3], [7,3,-1], [3,-1,4], [-1,4,1] and [4,1,6]. Their largest values are 7, 7, 4, 4 and 6.
Example 2
- Input:
- [5,-2,8], 1
- Output:
- [5,-2,8]
With k = 1 every window is one element, so the answer is the array itself.
Example 3
- Input:
- [-4,-9,-6], 3
- Output:
- [-4]
With k equal to the length there is one window. Its largest value is -4.
Constraints
1 <= nums.length <= 501 <= k <= nums.length-1000 <= nums[i] <= 1000
Run checks your code against the 3 examples. Submit checks it against all 173 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.