Incremental algorithm for maximum of last N entries in a series

You are lucky, there is a cool algorithm due to van Herk, Gil and Werman that computes a 1D dilation in constant time per element.

https://tpgit.github.io/UnOfficialLeptDocs/leptonica/grayscale-morphology.html

It can be made online with a buffer of 2N-1 elements.

The idea is simple. If you want to compute the maxima of four successive elements, you can compute incrementally the following maxima: a, ab, abc, abcd and e, ef, efg, efgh. Now combine...

abcd
 bcd e
  cd ef
   d efg

and repeat with the following elements.

Thanks everyone. Here is my Java implementation of the Deque-based algorithm (

import java.util.*;

/**
 *  Calculation is exclusive, i.e. immediately after adding an entry, the entry is not under consideration for min/max. <br>
 *
 *  Algorith outline: <br>
 *     at every step: <br>
 *    <br>
 *       if (!Deque.Empty) and (Deque.Head.Index <= CurrentIndex - T) then        <br>
 *          Deque.ExtractHead;                                                    <br>
 *       //Head is too old, it is leaving the window                              <br>
 *                                                                                <br>
 *       while (!Deque.Empty) and (Deque.Tail.Value > CurrentValue) do            <br>
 *          Deque.ExtractTail;                                                    <br>
 *       //remove elements that have no chance to become minimum in the window    <br>
 *                                                                                <br>
 *       Deque.AddTail(CurrentValue, CurrentIndex);                               <br>
 *       CurrentMin = Deque.Head.Value                                            <br>
 *       //Head value is minimum in the current window                            <br>
 */
public class RollingMinMax {

    private static class Entry {
        final int index;
        final double value;

        private Entry(int index, double value) {
            this.index = index;
            this.value = value;
        }

        @Override
        public String toString() {
            final StringBuilder sb = new StringBuilder("Entry{");
            sb.append("index=").append(index);
            sb.append(", value=").append(value);
            sb.append('}');
            return sb.toString();
        }
    }
    
    private final ArrayDeque<Entry> _minQueue;
    private final ArrayDeque<Entry> _maxQueue;
    private final int _windowSizeMin;
    private final int _windowSizeMax;
    private int _count= 0;
    private ArrayList<Double> _minHistory;
    private ArrayList<Double> _maxHistory;

    public RollingMinMax(int windowSizeMin, int windowSizeMax, boolean keepHistories) {
        _windowSizeMin = windowSizeMin;
        _windowSizeMax = windowSizeMax;
        if (_windowSizeMin < 0 || _windowSizeMax < 0) {
            throw new IllegalArgumentException("window size(s) too small");
        }
        _minQueue = new ArrayDeque<>(windowSizeMin);
        _maxQueue = new ArrayDeque<>(windowSizeMax);
        if (keepHistories) {
            _minHistory = new ArrayList<>();
            _maxHistory = new ArrayList<>();
        }
    }

    public void add(double datum) {
        final Entry entry = new Entry(_count, datum);

        // remove entriesthat are too old for consideration
        while (!_minQueue.isEmpty() && _minQueue.getFirst().index < _count - _windowSizeMin) {
            _minQueue.removeFirst();
        }
        while (!_maxQueue.isEmpty() && _maxQueue.getFirst().index < _count - _windowSizeMax) {
            _maxQueue.removeFirst();
        }

        // remove entries too small/large
        while (!_minQueue.isEmpty() && _minQueue.getLast().value > datum) {
            _minQueue.removeLast();
        }
        while (!_maxQueue.isEmpty() && _maxQueue.getLast().value < datum) {
            _maxQueue.removeLast();
        }

        enqueueCurrent(entry);

        ++_count;

        if (_minHistory != null) {
            _minHistory.add(getMin());
            _maxHistory.add(getMax());
        }

    }

    private void enqueueCurrent(Entry entry) {
        _minQueue.addLast(entry);
        _maxQueue.addLast(entry);
    }

    /** Double.NaN returned if not enough data added yet to compute. */
    public double getMin() {
        if (_count <= _windowSizeMin) {
            return Double.NaN;
        }
        double result = _minQueue.getFirst().value;
        return result;
    }

    public double getMax() {
        if (_count <= _windowSizeMax) {
            return Double.NaN;
        }
        double result = _maxQueue.getFirst().value;
        return result;
    }

    private ArrayList<Double> getMinHistory() {
        return _minHistory;
    }

    private ArrayList<Double> getMaxHistory() {
        return _maxHistory;
    }

    public String toString() {
        return "RollingMinMax[" + _windowSizeMin + ", "+ _windowSizeMax + "] min = " + getMin() + ", max =" + getMax() + ", count = " + _count;
    }

    public static void main(String[] ignored) {
        final ArrayList<Double> data = (ArrayList<Double>) Arrays.asList(
            1d, 4d, 6d,  0d, 9d, 5d, 3d, 6d, 8d, 10d, 13d, 15d, 8d, 14d, 12d, 5d, 6d, 8d, 10d, 7d, 5d, 3d, 2d
        );

        RollingMinMax calculator = new RollingMinMax(4, 6, true);
        System.out.println("calculator = " + calculator);

        int index = 0;
        for (double datum : data) {
            calculator.add(datum);
            System.out.println(index + "\t data=" + datum + ", min=" + calculator.getMin() + ", max=" +calculator.getMax());
            ++index;
        }
    }

}

Here's an idea that gives you the min and max of the last n elements of the array in constant time and adding new elements is of O(log n) time complexity.

1. Have a min and a max heap where you keep the last n elements of the array. These elements need to be nodes which you can reference later.
2. Have a queue in the form of a linked list or any data structure where FIFO operations are of constant time complexity. Keep track of the last n elements in this queue. Each element of the queue holds a reference to the corresponding entries in the min and max heaps.
3. Whenever a new element is added to the array do the following:

• Add it to the min and max heaps: log n operations.
• Enque the refernces to this new element in the queue: constant operation.
• Deque the reference of the element that goes out of the n length window from the queue: constant operation.
• remove that element from the min and max heap: log n operation.

The min and max heaps give you the current min and max elements of the last n elements at any time in constant time.

One possible optimization that wouldn't change the time complexity though is to combine the delete and add operations to a heap into one step. What you are going to do is to update the value of the reference that you want to delete from the heap with the value of the new element. Then run a swim and sink operation for the heap to hold its invariant. Then you will enque the dequed reference into the queue again, because it now holds the most recent value in the n length window.