#cs/cp The goal is to track the minimum or maximum of a sliding window. A monotonic deque gives $O(N)$ time and $O(k)$ space for a fixed window of size $k$. The key question is: *How do we know the next minimum or maximum as the window moves?* ## Sliding Max: Maintain a Monotonically Decreasing Deque Maintain a deque whose indices increase from left to right while their corresponding array values decrease. Store indices rather than values so expired elements can be removed from the window. When the window expands, remove values from the back that are no larger than the current value. A newer, larger value dominates them and remains in the window longer. Append the current index, then remove an index from the front if it is at most $i-k$. The front now holds the maximum for the current window. For a fixed-size window, at most one index expires per iteration. The deque preserves two invariants: indices increase from front to back, and their values decrease. The same invariants also apply to dynamically sized sliding-window problems. For a sliding minimum, reverse the value comparison and maintain a monotonically increasing deque. ## Example: Sliding Max Window ($k=3$) Denote `array[i] = n` as $n_i$. $ [\underbrace{1, 5, -1}_{5}, 4, 2] \to [1, \underbrace{5, -1, 4}_{5}, 2] \to [1, 5, \underbrace{-1, 4, 2}_{4}] $ $ \begin{align} i = 0; & \text{ deque } = [1_{0}] \\ i = 1; & \text{ deque } = [5_{1}] \\ i = 2; & \text{ deque } = [5_{1}, -1_{2}] \\ i = 3; & \text{ deque } = [5_{1},4_{3}]\\ i = 4; & \text{ deque } = [4_{3}, 2_{4}]\\ \end{align} $ ## Sliding Max Example Code ```python from collections import deque def maxSlidingWindow(nums, k): q = deque() # Stores indices result = [] for i, cur in enumerate(nums): # 1. Maintain decreasing order: pop dominated values from the back. while q and nums[q[-1]] <= cur: q.pop() q.append(i) # 2. Remove an index after it leaves the window. if q[0] <= i - k: q.popleft() # 3. The front is the maximum for the current window. if i >= k - 1: result.append(nums[q[0]]) return result ```