Solution: Tracing the Deque
Let’s trace. We use the running example:
values = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
Here is the candidate deque after processing each index, in order. Each box holds an index, and the value at that index is shown above the box.
i = 0 i = 1 i = 2
1 3 3 -1
┌────┐ ┌────┐ ┌────┬────┐
│ 0 │ │ 1 │ │ 1 │ 2 │
└────┘ └────┘ └────┴────┘
▲ ▲ ▲ ▲
first, last first, last first last
i = 3 i = 4 i = 5
3 -1 -3 5 5 3
┌────┬────┬────┐ ┌────┐ ┌────┬────┐
│ 1 │ 2 │ 3 │ │ 4 │ │ 4 │ 5 │
└────┴────┴────┘ └────┘ └────┴────┘
▲ ▲ ▲ ▲ ▲
first last first, last first last
i = 6 i = 7
6 7
┌────┐ ┌────┐
│ 6 │ │ 7 │
└────┘ └────┘
▲ ▲
first, last first, last
The outputs are:
[3, 3, 5, 5, 6, 7]
Let’s go through i = 4 step by step, because at this index we remove from the front and from the back.
Before processing 5 at index 4, the candidates are:
3 -1 -3
┌────┬────┬────┐
│ 1 │ 2 │ 3 │
└────┴────┴────┘
▲ ▲
first last
The current window after index 4 arrives is:
indices: 0 1 2 3 4 5 6 7
values: 1, 3, [-1, -3, 5], 3, 6, 7
Index 1 has expired, so it leaves from the front:
-1 -3
┌────┬────┐
│ 2 │ 3 │
└────┴────┘
▲ ▲
first last
Now the new value 5 arrives. It is larger than -3, so index 3 is evicted from the back. It is also larger than -1, so index 2 is evicted from the back:
(empty deque)
Then index 4 enters:
5
┌────┐
│ 4 │
└────┘
▲
first, last
The maximum of the current window is at the front: values[4], which is 5.