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 decreasing deque stores only indices still capable of becoming a window maximum. An older smaller candidate is dominated by a newer larger one, which also expires later. Indices are necessary to know when a candidate leaves.

Keeping only useful peak candidates

When 4 arrives after 3, 1, both older readings can be discarded: 4 is larger and will remain in the window longer. A later 2 cannot discard 4, so it waits behind it. Keep indices as well as values; an old 4 and a new 4 have different expiry times. The front candidate is the current peak after expired indices are removed.

indices := []int{1, 3}
leftBoundary := 2
if len(indices)>0 && indices[0]<leftBoundary { indices=indices[1:] }

Why the cleanup stays linear

Each index enters once and leaves at most once, yielding amortized O(n) work despite a nested cleanup loop. Equal maxima need a deliberate keep-or-replace policy, but the output value is the same. This suits rolling peaks; it does not provide arbitrary range queries or support changes to old positions.

Every index is appended once and removed at most once, from either end. Total candidate maintenance is O(n), with O(w) working space for width w, excluding returned peaks. A median or an arbitrary interval query needs more information than this dominance rule retains.

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