Dynamic Programming21 sections · 916 units
Open in Course

Monotonic Queue vs Other Techniques

When to use what

Monotonic queue: window min/max with fixed window size. O(n)O(n) time. Segment tree with lazy propagation: arbitrary range queries, supports updates. O(nlogn)O(n \log n) time. Sparse table: static range min/max queries. O(nlogn)O(n \log n) preprocessing, O(1)O(1) query.

When you have a sliding window (fixed size, sequential iteration), monotonic queue is the cleanest and fastest. Use the others for more general range query problems.