arraysqueues
A deque keeps sliding-window maxima efficient
Anonymous
For a sliding-window maximum, store indices in decreasing order of their values. Remove indices that fall left of the window, then discard smaller values from the back before adding the new index. Each index enters and leaves once, so total work is O(n); the deque can hold O(n) indices.
0