Find the maximum of every window of 3 values. The deque holds indices from the window whose values could still be the maximum, front to back, and the front is always the answer.
Finding the maximum of every window of 3 values with a deque that keeps the maximum at its front.
The deque is empty, so 1 goes in and is the front.
The deque is empty. 1 is pushed and becomes the front.
3 enters. The back of the deque is 1, which is not larger than 3 and will leave the window sooner. It can never be the maximum again, so pop it.
3 enters and 1 at the back is dominated, so it is popped.
The deque is empty, so 3 goes in and is the front.
The deque is empty. 3 is pushed and becomes the front.
-1 enters. The back of the deque is 3, which is larger than -1, so it stays. Push -1 behind it.
-1 enters. 3 at the back stays and -1 is pushed behind it.
Window 0 to 2 is complete. Its maximum is the front of the deque, 3, read in O(1).
The maximum of window 0 to 2 is 3, the front of the deque.
-3 enters. The back of the deque is -1, which is larger than -3, so it stays. Push -3 behind it.
-3 enters. -1 at the back stays and -3 is pushed behind it.
Window 1 to 3 is complete. Its maximum is the front of the deque, 3, read in O(1).
The maximum of window 1 to 3 is 3, the front of the deque.
The window slides to indices 2 to 4. 3 at index 1 was the front but has left the window, so drop it.
The window moves to indices 2 to 4. 3 has left the window and is removed from the front of the deque.
5 enters. The back of the deque is -3, which is not larger than 5 and will leave the window sooner. It can never be the maximum again, so pop it.
5 enters and -3 at the back is dominated, so it is popped.
5 enters. The back of the deque is -1, which is not larger than 5 and will leave the window sooner. It can never be the maximum again, so pop it.
5 enters and -1 at the back is dominated, so it is popped.
The deque is empty, so 5 goes in and is the front.
The deque is empty. 5 is pushed and becomes the front.
Window 2 to 4 is complete. Its maximum is the front of the deque, 5, read in O(1).
The maximum of window 2 to 4 is 5, the front of the deque.
3 enters. The back of the deque is 5, which is larger than 3, so it stays. Push 3 behind it.
3 enters. 5 at the back stays and 3 is pushed behind it.
Window 3 to 5 is complete. Its maximum is the front of the deque, 5, read in O(1).
The maximum of window 3 to 5 is 5, the front of the deque.
6 enters. The back of the deque is 3, which is not larger than 6 and will leave the window sooner. It can never be the maximum again, so pop it.
6 enters and 3 at the back is dominated, so it is popped.
6 enters. The back of the deque is 5, which is not larger than 6 and will leave the window sooner. It can never be the maximum again, so pop it.
6 enters and 5 at the back is dominated, so it is popped.
The deque is empty, so 6 goes in and is the front.
The deque is empty. 6 is pushed and becomes the front.
Window 4 to 6 is complete. Its maximum is the front of the deque, 6, read in O(1).
The maximum of window 4 to 6 is 6, the front of the deque.
7 enters. The back of the deque is 6, which is not larger than 7 and will leave the window sooner. It can never be the maximum again, so pop it.
7 enters and 6 at the back is dominated, so it is popped.
The deque is empty, so 7 goes in and is the front.
The deque is empty. 7 is pushed and becomes the front.
Window 5 to 7 is complete. Its maximum is the front of the deque, 7, read in O(1).
The maximum of window 5 to 7 is 7, the front of the deque.
Answer [3, 3, 5, 5, 6, 7]. Every value was pushed once and popped at most once, 8 pushes and 7 pops for 8 values, so the whole scan is O(n) with a deque of at most 3.
The maximum of each window is [3, 3, 5, 5, 6, 7]. 8 pushes and 7 pops in all.