Monotonic deques

A latency dashboard shows the maximum of the latest w readings. A running sum can subtract a reading when it expires. A running maximum cannot: once the peak leaves, the dashboard needs to know which remaining reading replaces it.

Rescanning each window works, but adjacent windows share almost all their data. A monotonic deque keeps the readings that could still become a future maximum and discards the ones that cannot.

A rolling peak needs a replacement

A monotonic deque retains only values that could become a future window maximum. Rescanning each width-w window is a clear O(nw) baseline, but consecutive windows overlap heavily. A new value can make older candidates permanently unnecessary.

Keep candidate indices rather than values so equal readings with different expiry positions remain distinguishable. The deque's values decrease from front to back.

Keeping only useful peak candidates

Remove expired indices from the front. Before adding a new index, remove older back candidates whose values are no larger. The newer value is at least as large and remains in future windows at least as long, so those candidates can never win again. After cleanup, the front is the current full window's maximum.

For [9, 8, 7, 6] with width 2, descending values remain candidates until their indices expire, yielding maxima 9,8,7. Equal values can be replaced by their newer occurrence without changing maxima. Record output only once a full window exists.

JavaScript has no built-in deque type. Repeated Array.shift() can move many elements and lose the linear bound. Use a bounded ring buffer or explicit head/tail management with a storage-reclamation policy; leaving every expired slot in a growing array does not meet an O(width) storage claim.

const loads = [4, 4, 1];
const older = 0, newer = 1;
console.log(loads[older] === loads[newer]); // true
console.log(newer > older); // true: same value, later expiry

Why the cleanup stays linear

Every index enters once and leaves at most once, so all front/back removals total O(n). Final time is O(n), auxiliary deque storage O(width), excluding output. Use this for moving extrema. Sum windows need only addition/subtraction; arbitrary range queries call for a different structure.

When the old peak expires, the dashboard already has its next eligible candidate.