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

Produce a maximum for every full fixed-width window. Old maxima must expire when their indices leave the window, even when equal-valued peaks remain.

Rescanning each window costs O(n*width). A monotonic deque retains only candidates that can still become a future maximum. Storing values alone cannot tell which equal occurrence has expired.

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.

The deque holds candidate indices in increasing time order and decreasing value order. Expire out-of-window indices at the front, discard dominated values at the back, then read the front. Storing only values loses which repeated maximum has expired. Each index is pushed/popped at most once: O(n) time and O(width) space.

The candidate needs position as well as value. Equal peaks at different indices have different lifetimes:

import java.util.*;

class Example {
    public static void main(String[] args) {
        long[] values = {4, 4, 1};
        Deque<Integer> candidates = new ArrayDeque<>();
        candidates.addLast(0);
        candidates.addLast(1);
        int newLeft = 1;
        assert candidates.peekFirst() < newLeft;
        assert values[candidates.peekLast()] == 4;
    }
}

Index zero must expire even though its value equals a later surviving maximum. A complete deque implementation also discards dominated back candidates and emits only full windows; neither rule is replaced by a heap of bare values.

Why the cleanup stays linear

Monotonic frontiers support rolling extrema and similar online summaries. Their linear bound comes from each index entering and leaving at most once, not from a claim that every individual loop iteration does constant work.

Return each full window maximum in start order. Negative values and repeated maxima are valid. Empty input or width greater than length yields an empty list. Width <= 0 always raises IllegalArgumentException, even on empty input.

Numeric arithmetic uses long; indices use int. Inputs follow the declared types and contain no null elements unless the API permits them. Preserve caller-owned collections, including on failure, and use IllegalArgumentException for the documented invalid arguments.

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