You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
Return the max sliding window.
Example 1:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3 Output: [3,3,5,5,6,7] Explanation: Window position Max --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7
Example 2:
Input: nums = [1], k = 1 Output: [1]
Example 3:
Input: nums = [1,-1], k = 1 Output: [1,-1]
Example 4:
Input: nums = [9,11], k = 2 Output: [11]
Example 5:
Input: nums = [4,-2], k = 2 Output: [4]
Constraints:
1 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^41 <= k <= nums.length
The description was taken from https://leetcode.com/problems/sliding-window-maximum/.
#O(N) Time, O(N) Space
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
if not nums:
return []
queue, output = collections.deque(), []
for i in range(0, len(nums)):
if i >= k and queue[0][1] == i-k:
queue.popleft()
while queue and nums[i] >= queue[-1][0]:
queue.pop()
queue.append((nums[i],i))
if i >= k - 1:
output.append(queue[0][0])
return outputThis problem comes down to finding the nearest maximum value. With requirements like that, a Monotonic Queue or a Monontonic Stack are great approaches.
We will use a Monotonic Queue for this approach.
What we will do is traverse the input and each time we find a value that is greater than the rightmost value in the queue, we will remove the smaller value from the queue. This way, our current maximum is always in the leftmost position. Once we have reached the end of the window, we can append that leftmost position to the output. Also, once we begin each new iteration we can just check if the leftmost value in the queue is from a previous window and pop it.
By doing this, we will have the maximum value in each window.
First off, if we have no input then we have no maximums. We will return nothing.
if not nums:
return []
Otherwise, we will initialize the queue and the output array.
queue, output = collections.deque(), []
Next, we will start iterating through the input.
for i in range(0, len(nums)):
At the beginning of each iteration, we will see if we need to evict any old tenants from the queue.
If we have gotten past the first window, and the leftmost position is from the previous window, we are looking at a previous sliding window maximum. We will need to kick this value out of the queue so that we don't consider it for the current window.
This is the reason why a queue is better than the stack alternative for this question because when we pop a left value from a stack, the rest of the indices need to shift over, wherein a queue they won't have to.
if i >= k and queue[0][1] == i-k:
queue.popleft()
Otherwise, we will look at the current value and see if it is greater than the rightmost value in our queue. We may have more than one value in the queue. If it is, then we will do this for any value in the queue that is lower than the current one. We already kicked any old values out of the queue previously in the iteration so there is no reason to consider any of the lower values in the queue as the current sliding window maximum when we now have this greater value that we are looking at.
This is also good because if there is a greater value than the current number, it won't be popped out and the current number will act as a backup plan in the scenario that we evict the greater value from the window later when it becomes too old to be considered for the current window.
while queue and nums[i] >= queue[-1][0]:
queue.pop()
Once we have evicted any old and lower values from the queue, we will append the current value as well as its index so we can tell which window it belongs to.
queue.append((nums[i],i))
If we have gotten to or past the first window, we will append the current maximum to the output which is the leftmost value in the queue.
if i >= k - 1:
output.append(queue[0][0])
Once we have finished traversing the array, we will have our array of sliding window maximums which we can now return.
return output