← Back to problems
k = 3
Sliding Window Peak Query
AeroSpace • satellite telemetry • monotonic deque
Readings arrive one at a time. ingest(value) takes the next one. get_peak() returns the maximum of the last k readings, or nothing until a full window exists. The deque stays decreasing by value, so the front is the peak. Each reading is pushed once and popped once.
IngestO(1) amort.
SpaceO(k)
Step0/0
Ready
Press Play or Step. Window of 3. Readings: 5, 2, 8, 1, 9, then 4, 3, 1 so the old peak can age out.