Deque extrema are still one pass
Updated
Sliding-window max with a decreasing index deque still walks i=0..n-1 once. Each index is pushed once and popped at most once (from back as dominated, or from front as expired).
What to focus on
Deque ops total O(n). That is the same amortized linear scan, with extra O(1) work per pop. It is not a second pass over each window.
Worked examples
pushes
a = [4, 1, 9, 1]- push 0, push 1, pop 1, pop 0, push 2, push 3
- each index pushed once
Result: 4 pushes
pops dominated
a = [4, 1, 9, 1], i=2- 9 pops index 1 then 0 from the back
- those indices never return to the deque
Result: each popped ≤ once
vs rescan
a = [4, 1, 9, 1], length 2 max without deque- three windows each scan 2 cells
Result: more cell visits; deque is still one i-pass
Try it
Write dequeMax(a, k). a is an array of integers. k is the window length. The deque stores indices of a[L..R], front = current max. Each index is pushed once and popped at most once. Return the window maxes. Total deque ops must be O(n). On [4, 1, 9, 1].
a is nonempty, length ≥ 2. 1 ≤ k ≤ n.