Sliding Window Maximum

Find the maximum element in each window of size K using a Deque.

1
0
3
1
-1
2
-3
3
5
4
3
5
6
6
7
7

Deque (Indices)

Empty

Result Array

Status: Ready
Speed

Algorithm Logic

1function maxSlidingWindow(nums, k):
2 deque = [] // indices
3 result = []
4 for i, n in enumerate(nums):
5 // 1. Remove out of window
6 if deque and deque[0] < i - k + 1:
7 deque.shift()
8 // 2. Remove smaller elements from rear
9 while deque and nums[deque[-1]] < n:
10 deque.pop()
11 deque.push(i)
12 // 3. Add to result
13 if i >= k - 1:
14 result.push(nums[deque[0]])
15 return result

Parameters