Indices on the stack, a queue for windows

Putting the index on the stack instead of the value gives you two things at once: the value (values[i]) and the place. In questions like "how many days to wait?" the answer is the difference of two places; had you stored the value you could not work it out.

1from collections import deque
2window = deque()
3for i, v in enumerate(values):
4    while window and values[window[-1]] <= v:
5        window.pop()
6    window.append(i)
7    if window[0] <= i - size:
8        window.popleft()

For the largest of a sliding window you need to drop elements from both ends: from the back, those smaller than the newcomer (they can never be a window's largest again); from the front, the one that has left the window. A deque does either end in one step; the window's largest is always at window[0].

A stack uses one end (last in, first out), a queue both (first in, first out). pop(0) at the front of a list shifts every remaining element; when you need a queue, use a deque.

Tasks