◄ WORLD V · SONNY 5DART 315 · a helldive at the net

SLIDING-WINDOW MAXIMUM the problem the monotonic queue was built for — extrema on the move

Given a stream and a window width, report the maximum of every window as it slides. It is the canonical streaming problem: the answer at each step depends only on a bounded suffix, yet the naive solution stubbornly re-reads the whole window each time. The point of isolating it as its own dart is that the problem is what makes the monotonic-queue mechanism (dart 314) worth its cleverness — and that the two are not the same thing. A dozen correct mechanisms solve this (rescan, a balanced tree, a sparse table, the deque); they agree on every answer. That agreement is exactly the tell the B39 panel named: when many correct mechanisms converge, the shared truth is a property of the problem, witnessed — not a mechanism any one of them enacts.

THE TECHNIQUE max over each window; many mechanisms, one answer

The first window of the same stream. The demo reports its maximum — a value every correct method agrees on: live demo







  
HISTORY & CREDIT the streaming-extrema problem

  
“The clever algorithm and the problem it solves are the same idea.” — they are not: the problem admits many correct solutions that all agree, and that agreement is the witness-signature, not the mechanism. cited

  
the problem · window extrema, a staple of streaming and DP-optimization.
the solvers · rescan (O(nk)), a heap/BST (O(n log k)), a sparse table (O(1) query after O(n log n) prep), the monotonic deque (O(n)) — all return the identical maxima.
the lesson · convergence of correct mechanisms = a witnessed problem-property (B39), not an enacted mechanism-property.

  
Four correct methods, one sequence of answers. The agreement belongs to the problem, not to any solver. streaming extrema






  
RECOMMEND FOR I-13 the window maximum, on the compiler

  
On the canonical compiler, the maximum of the first window [1,3,−1] is 3 — the same value any correct solver returns:

  
$ i13 run op_windowmax.i13   # max of the first window
RUN OK · 103 step(s) · peak stack 7 · call depth 4
first_window_max = 3      -- rescan, heap, sparse-table, deque all agree

  
Recommend as a witness, not a keeper: this dart exists to hold the B39 lesson in plain sight. The window maximum is a property of the problem; rescan, heap, sparse table, and the monotonic deque all compute it and all agree. That convergence of correct mechanisms is the holds-not-enacted signature — the same reason the interpolators (Newton = Neville = barycentric, batch 39) were witnessed, not enacted. The mechanism worth keeping, if any, is the deque's eviction (dart 314), not the answer they share. i13 computes the max 3; that it is easy and universal is precisely why it is a witness.