239. Sliding Window Maximum — LeetCode(Python)
I got you!
Problem:
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] 7Example 2:
Input: nums = [1], k = 1
Output: [1]Constraints:
1 <= nums.length <= 105-104 <= nums[i] <= 1041 <= k <= nums.length
Solution:
q = collections.deque()
res = []
for r, n in enumerate(nums):
while q and nums[q[-1]] <= n:
q.pop()
q.append(r)
# remove 1st element if it is outside the window
if r - q[0] == k:
q.popleft()
# if window has k elements, add to results. this is invalid only for first k elements
if r + 1 >= k:
res.append(nums[q[0]])
return resExplanation —
We use a sliding window technique here — duh!
We use the deque data structure to keep track of the elements in the window in a monotonically decreasing order.
When we come across a new number, we compare it to the elements in the deque and pop elements in the deque until we find a number in the deque that is greater than this new number.
After that, we add this new number in the deque.
Then, we remove the 1st element in the deque if it is outside the window. We use if instead of while since we are only sliding the window one element at a time.
If our window has k elements, we add the top of the deque to our result res.
Finally, we return res.
Time and Space Complexity —
Traversing the array once is a linear time operation.
Also, our deque can have a maximum of k elements in the worst case.
Thus, if n is the length of the array nums,
Time Complexity: O(n)
Space Complexity: O(k)
