927. The Highest Reading in the Last w Seconds

A sensor produces n readings. Reading i arrives at time t[i] and has value v[i]. Times are given in non-decreasing order and several readings may share a time.

After each reading, print the largest value among all readings whose time lies in the window (t - w, t], where t is the time of the reading just made. The far end is EXCLUSIVE: a reading at exactly t - w has expired.

``` w = 3, readings (1,4) (2,7) (4,2) (5,1) (9,3) -> 4 / 7 / 7 / 2 / 3 at time 5 the window is (2, 5], so the 7 at time 2 has just expired

w = 1, readings (5,9) (5,4) (5,6) -> 9 / 9 / 9 ```

## The heap answer, and why it loses

A max-heap with lazy deletion works. Push (value, time), and before reading the top, discard entries whose time has fallen out of the window. Each entry is pushed once and popped at most once, so the whole run is O(n log n).

It is correct and it is the wrong tool, for a reason specific to this shape: THE ORDER OF REMOVALS IS KNOWN IN ADVANCE. Times only increase, so readings expire strictly in arrival order. A structure that has to be told "give me the largest" while entries leave in an arbitrary order needs a heap; one where entries leave oldest-first does not.

## The method: a monotonic deque

Keep a double-ended queue of reading INDICES whose values decrease from front to back. Two rules, in this order:

after appending reading i: drop from the BACK every index whose value is <= v[i], then push i before reading the answer: drop from the FRONT every index whose time is <= t[i] - w answer = value at the front

The back rule is the domination argument: if j < i and v[j] <= v[i], then j is no better on value and expires no later than i, so no future window will ever have j as its answer while i is available. j is discarded permanently, not lazily.

The front rule is what a stack cannot do: entries leave because they are too OLD, not because something better arrived.

## What it costs, side by side

heap with lazy deletion monotonic deque per reading O(log n), pushes and pops amortised O(1) total at n=2e5 about 3.5 * 10^6 with a about 4 * 10^5 with a large constant per compare tiny one memory every reading, until it only the useful candidates, surfaces at the top often a handful

Both finish inside a second here. The deque is the right answer because it uses a property the problem actually has, and reaching for the heap means not having noticed it.

## How this differs from the fixed-index window

Problem #193 slides a window of exactly k CONSECUTIVE positions, so the expiry test is "index <= i - k" and the window always holds k values. Here the window is fixed in TIME, not in count: readings arrive irregularly, several may share a timestamp, and a long quiet gap can leave the window holding a single reading. The expiry rule becomes a loop over times rather than a single index comparison, and the number of live readings varies.

Everything else, including the domination argument, is identical, which is the point of seeing it twice.

## The boundary that breaks a careless implementation

Expire from the front BEFORE reading the answer, not after pushing. The reading just pushed is always inside its own window, so the deque can never empty at the moment the answer is read, but only if the two steps are in this order.

The window is half-open: a reading at exactly t - w is OUT. The test is time <= t - w, and writing < keeps an expired reading alive. The sample with w = 3 at time 5 exists to catch exactly that.

Pop from the back on <=, not <. Using < is still correct, because equal values give the same answer, but the deque then accumulates duplicates and grows without bound on a constant input. It is an efficiency bug, not a correctness one, which makes it hard to notice.

## Overflow

Times and values reach 10^9 in magnitude, and the one arithmetic expression is t - w, which with t as small as 1 and w as large as 10^9 reaches -999999999. A signed 32-bit integer holds down to -2147483648, so that fits. Nothing is added or multiplied, so there is no overflow in this problem.

## Related problems

Problem #1913 counts the hits inside a time window with a PLAIN queue and no ordering at all, because a count survives a removal from the front while a maximum does not. Problem #863 solves a dynamic program whose window is fixed in index with the same deque, and its statement makes the same comparison against a heap. Problems #119, #193 and #194 are the fixed-index originals.

## Cost

Time O(n). Space O(n).

Constraints - `1 ≤ n ≤ 200000` - `1 ≤ w ≤ 10^9` - `1 ≤ t[i] ≤ 10^9`, non-decreasing - `-10^9 ≤ v[i] ≤ 10^9`