Proficient Level
Implement the slidingWindowMaximumDeque method that returns maximum values for every sliding window of size k.
The input contains an integer array nums, its length size, and a window size k.
Your task is to move a window of size k from left to right and return the maximum value from each window.
For example, for [1,3,-1,-3,5,3,6,7] with k = 3, the window maximum values are [3,3,5,5,6,7].
Example 1
Input
nums (int[]) =
[1,3,-1,-3,5,3,6,7]size (int) =
8k (int) =
3Returns (int[])
[3,3,5,5,6,7]Example 2
Input
nums (int[]) =
[1]size (int) =
1k (int) =
1Returns (int[])
[1]Example 3
Input
nums (int[]) =
[9,11]size (int) =
2k (int) =
2Returns (int[])
[11]Use a deque to store indexes of useful elements.
The deque is kept in decreasing order of values, so the front always points to the maximum value of the current window. Before adding a new index, remove smaller values from the back because they can never become the maximum while the current value is inside the window.
Also remove indexes from the front when they move outside the current window.
Pseudocode:
function slidingWindowMaximumDeque(nums, size, k):
deque = empty deque
result = empty array
for i from 0 to size - 1:
while deque is not empty and front(deque) <= i - k:
remove front from deque
while deque is not empty and nums[back(deque)] <= nums[i]:
remove back from deque
add i to back of deque
if i >= k - 1:
append nums[front(deque)] to result
return resultReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run