statistics – Sliding window max/min algorithm without dynamic allocations

I’m working on a suite of DSP tools in Rust, and one of the features of the library is a collection of windowed statistics (mean, rms, min, max, median, etc) on streams of floating-point samples. The user provides an iterator of floats and a fixed-size mutable slice/array of floats as inputs, and get back a iterator that lazily calculates the desired stat one sample at a time. The contents of the float slice/array become the initial window, and can be used as scratch space internally. This slice/array also determines the sliding window size.

// A sliding mean with a window size of 64, initially filled with 0.42.
let sample_iter = /* an iterator that yields floats */;
let buffer = (0.42; 64);
let sliding_mean_iter = SlidingMean::new(sample_iter, buffer);

I’d ideally like to have my library also usable in an embedded environment, and so far I’ve been able to do so by not using any dynamic memory allocations.

As of now, I have efficient mean and rms implementations, but I’m stumped on the windowed min/max. Looking up sliding window min/max algorithms online(1)(2), I see that:

  1. A naive approach of scanning the window after each update leads to a O(nk) runtime, where n is the length of the input iterator and k is the window length. This feels like it could be inefficient for larger window sizes.
  2. Using a deque allows for an efficient implementation of O(n) (with amortized insertion of O(1)), but using a deque would require dynamic allocations.
  3. Since the passed-in buffer is overloaded to both set the initial window contents as well as to serve as scratch space, I can’t mess with the type of that, it has to stay as a slice/array of plain floats. This means I can’t make it an array of (int, float) to store array indices alongside the data, for example.

Are there any clever tricks or optimizations I can use to have my cake (efficient sliding min/max) and eat it too (avoid having memory allocations)?

EDIT: For reference, since it came up in the comments, here’s a walkthrough example of a sliding max with window length 3:

Initial samples: {3 4 3 1 5 2 7 3 4 1}

Step 1: {(3 4 3) 1 5 2 7 3 4 1} -> The max of (3 4 3) is 4.
Step 2: {3 (4 3 1) 5 2 7 3 4 1} -> The max of (4 3 1) is 4.
Step 3: {3 4 (3 1 5) 2 7 3 4 1} -> The max of (3 1 5) is 5.
Step 4: {3 4 3 (1 5 2) 7 3 4 1} -> The max of (1 5 2) is 5.
Step 5: {3 4 3 1 (5 2 7) 3 4 1} -> The max of (5 2 7) is 7.
Step 6: {3 4 3 1 5 (2 7 3) 4 1} -> The max of (2 7 3) is 7.
Step 7: {3 4 3 1 5 2 (7 3 4) 1} -> The max of (7 3 4) is 7.
Step 8: {3 4 3 1 5 2 7 (3 4 1)} -> The max of (3 4 1) is 4.
Done.

The output is therefore {4 4 5 5 7 7 7 4}.