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

Keep indices of values that can still become a window maximum. A newer value at least as large makes an older candidate unnecessary: the newer value expires later and is never smaller. Remove such candidates from the back; remove expired indices from the front.

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.

std::deque<std::size_t> candidates;
// Compare loads[candidates.back()], not the numeric index itself.

Why the cleanup stays linear

Indices distinguish equal-valued entries with different expiration times. The front is the maximum only after expired indices have been removed. Every index enters once and leaves at most once, so repeated-looking inner loops still cost O(n) total. Memory is bounded by the window width. Validate positive width before the empty-input shortcut; an invalid width does not become valid when there are no loads. A width larger than the input has no complete window and yields an empty result.

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.

Use the supplied Int, Vec, and Opt aliases. Numeric arithmetic fits signed long long; absence uses std::nullopt, and documented invalid inputs throw std::invalid_argument. Keep caller-owned containers unchanged.

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