Maintain min or max of the window
Updated
Min/max of a[L..R] can be rescanned in O(R-L+1), or kept in a deque of candidate indices. The deque stores indices. Front = current extreme.
What to focus on
Decreasing deque for max: pop the back while a[back] <= a[i], then push i. Pop the front when its index leaves the window. Recompute is simpler. The deque is O(1) amortized per index.
Worked examples
recompute length 2
a = [4, 1, 9, 1]- [0,1] max 4 min 1
- [1,2] max 9 min 1
- [2,3] max 9 min 1
Result: maxes 4, 9, 9
deque decreasing
a = [4, 1, 9, 1], max deque of indices- i=0 → [0]
- i=1 1<4 → [0,1]
- i=2 9 pops 1 then 0 → [2]
- i=3 1<9 → [2,3]
Result: deque [2, 3], front max 9
front expires
a = [4, 1, 9, 1], w=2, i=2, deque was [0,1]- window [1,2]
- front 0 < 1, popFront
- 9 pops 1, push 2 → [2]
Result: window max a[2]=9
Try it
Write windowMax(a, k). a is an array of integers. k is the window length. L and R bound a[L..R], which the window includes. The deque stores indices, front = current max. Compute length-2 max by rescan on [4, 1, 9, 1]. Then maintain a decreasing index deque through i=0..3. Print front 9 after 9 enters. Maxes of length-2 windows are 4, 9, 9.
a is nonempty, length ≥ 2. Window length k satisfies 1 ≤ k ≤ n.