Stack and monotone deque · HTML
Deque indexes increase by position and their values are monotone in the target direction. At i, remove heads with index≤i-k, pop tail candidates no better than a[i], then append i.
Recognition signals
- Every length-k window needs its maximum or minimum.
- Candidates expire by leaving the window and are also dominated by better new values.
- A DP transition takes the best prior state within a bounded lookback.
- A lazy heap works but pays log k per update.
False friends
| Signal | Why it is different |
|---|
| Nearest greater element | Without positional expiration, a monotonic stack is more direct. |
| Window sum or frequency | Reversible aggregates need only an ordinary sliding window, not dominance eviction. |
Core invariant
Deque indexes strictly increase and lie in the current window; values are monotone, the front is the current extremum, and every tail-popped index can never beat the newer index in any future shared window.
State, transition, and processing order
| Item | Definition |
|---|
| State | Index deque, current index i, window width k, and output or DP state. |
| Transition | Remove expired heads, remove tail candidates dominated by the current value, append i, and read the front once the window matures. |
| Frontier / order | A Pareto chain of current-window indexes that can still become an extremum now or in a future overlapping window. |
Python skeleton
from collections import deque
def window_max(values, k):
if k <= 0 or k > len(values):
return []
dq, answer = deque(), []
for i, value in enumerate(values):
while dq and dq[0] <= i - k:
dq.popleft()
while dq and values[dq[-1]] <= value:
dq.pop()
dq.append(i)
if i >= k - 1:
answer.append(values[dq[0]])
return answer
Correctness sketch
- Head expiration keeps every stored index inside the current window.
- If an older value is no larger than the new value, it expires sooner and is never better in a shared future window, so tail removal is safe.
- Remaining values are monotone; the front is unexpired and undominated, hence exactly the window maximum.
Complexity
| Time | Space | Parameters |
|---|
| O(n) | O(k) | Each index enters once and leaves from one end at most once; the deque stores at most k current-window indexes. |
Edge cases
- For k=1 the output equals the input.
- For k=n there is one extremum.
- Define a contract for invalid k.
- Using <= for maximum tail eviction retains the newer equal value, which expires later.
Error patterns
| Pattern | Why it fails / fix |
|---|
| Storing values instead of indexes | Expiration cannot be detected and duplicate values cannot be distinguished. |
| Using < i-k for expiration | Index i-k is already outside [i-k+1,i], so the comparison must include equality. |
| Reversing tail monotonicity | For maxima, remove tail values no greater than the new value. |
Selection and exclusion rules
- Use a monotonic deque for min or max over every fixed contiguous window.
- Use a monotonic stack for nearest dominance without a window width.
- Use a heap when candidate priority is complex and cannot be reduced to one-value dominance.
| Relation | Template | Boundary |
|---|
| extremum state component | Fixed-size sliding window | A fixed window moves from an invertible sum to noninvertible min/max. |
| extrema/prefix enhancement | Variable-size sliding window | The window must retain an extremum or optimal historical prefix. |
| ordered-candidate alternative | Top-K bounded heap | Several priority-ranked candidates are needed rather than one dominance chain. |
| same container, different invariant | 0-1 BFS | Do not confuse priority buckets with a window-extrema deque. |
Original micro-example
| Part | Detail |
|---|
| Result | The two window maxima are [3,3]. |
| Setup | Values [2,1,3,2], k=3; report each window maximum. |
| Trace | At 3, pop both 1 and 2 from the tail, leaving index 2; the next 2 joins but 3 remains front. |
Recall prompts
My notes