Use a deque to maintain window candidates in increasing/decreasing order for O(1) queries per slide
Pop from back to maintain monotonicity and pop from front when index leaves the window; front holds the answer.
Use for sliding window max/min, shortest subarray with sum ≥ K using prefix sums, and other windowed monotonic predicates.
Window max/min by keeping a decreasing/increasing deque of indices; drop out-of-window from the front and weaker candidates from the back.
# Monotonic Deque Template (Sliding Window Max)
from collections import deque
def max_sliding_window(nums, k):
dq = deque() # indices, decreasing by value
res = []
for i, v in enumerate(nums):
while dq and dq[0] <= i-k: dq.popleft()
while dq and nums[dq[-1]] <= v: dq.pop()
dq.append(i)
if i >= k-1: res.append(nums[dq[0]])
return resMaintain decreasing (max) or increasing (min) deque of indices
from collections import deque
def max_sliding_window(nums, k):
dq = deque() # indices, decreasing by value
res = []
for i, v in enumerate(nums):
while dq and dq[0] <= i - k:
dq.popleft()
while dq and nums[dq[-1]] <= v:
dq.pop()
dq.append(i)
if i >= k - 1:
res.append(nums[dq[0]])
return resUse increasing deque over prefix sums to find shortest valid range
from collections import deque
def shortest_subarray_at_least_k(nums, k):
# Works with negatives using prefix sums + increasing deque
n = len(nums)
pref = [0]
for x in nums:
pref.append(pref[-1] + x)
ans = n + 1
dq = deque()
for i, s in enumerate(pref):
while dq and s <= pref[dq[-1]]:
dq.pop()
while dq and s - pref[dq[0]] >= k:
ans = min(ans, i - dq.popleft())
dq.append(i)
return ans if ans <= n else -1Maintain lower/upper hull of lines to query minima/maxima
# Monotone CHT for increasing slopes and increasing x queries
class CHT:
def __init__(self):
self.lines = [] # (m, b)
def bad(self, l1, l2, l3):
# Remove middle if intersection(l1,l2) >= intersection(l2,l3)
return (l3[1]-l1[1]) * (l1[0]-l2[0]) <= (l2[1]-l1[1]) * (l1[0]-l3[0])
def add(self, m, b):
self.lines.append((m, b))
while len(self.lines) >= 3 and self.bad(self.lines[-3], self.lines[-2], self.lines[-1]):
self.lines.pop(-2)
def query(self, x):
# Assuming non-decreasing x
while len(self.lines) >= 2 and self.f(self.lines[0], x) >= self.f(self.lines[1], x):
self.lines.pop(0)
return self.f(self.lines[0], x)
def f(self, line, x):
return line[0]*x + line[1]Each index enters and leaves deque once.
Deque stores up to window size indices.