Monotonic Deque
A deque holding indices in decreasing value order. The front is always the window maximum.
Sliding WindowO(n)New3 problems
18
mastery
Trigger phrases
If a problem statement sounds like one of these, try this pattern first.
sliding window maximum
constrained subsequence sum
The template
Get this into muscle memory, then adapt the condition per problem.
const dq: number[] = [];
for (let i = 0; i < n; i++) {
while (dq.length && a[dq[dq.length - 1]] <= a[i]) dq.pop();
dq.push(i);
if (dq[0] <= i - k) dq.shift();
if (i >= k - 1) out.push(a[dq[0]]);
} Watch Sliding Window MaximumIf you are stuck
The generic hint ladder for this pattern, in order.
- 1A heap works but costs log n per step. Can you do better?
- 2A smaller element that arrives later makes every earlier smaller element useless.
- 3Evict from the front when the index falls out of the window.
Drill it
Every problem in the bank that uses this pattern.
0 / 3 solved