序列中最后 N 个条目最大值的增量算法

Question

有人知道数组最后 n 个条目的最大值（或最小值）的有效增量算法吗？

我所说的“高效”和“增量”是指当一个新元素被添加到数组中时，我们会做一些比仅仅搜索最后的 n 个条目更聪明的事情！理想情况下，相对于 n（当然 < O(n)），它应该是恒定的复杂度 O(1)。显然每个数组条目可以存储一个或多个数据以帮助计算。计算出的最大值必须适用于所有数组条目，而不仅仅是最后一个条目。

谢谢

Answer 1

你很幸运，van Herk、Gil 和 Werman 提出了一个很酷的算法，可以计算每个元素在恒定时间内的一维膨胀。

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

可以用2N-1个元素的buffer在线制作

这个想法很简单。如果要计算四个连续元素的最大值，可以递增地计算以下最大值：a、ab、abc、abcd 和 e， ef、efg、efgh。现在结合...

abcd
 bcd e
  cd ef
   d efg

并重复以下元素。

Answer 2

这里有一个想法，可以在常数时间内给出数组最后 n 个元素的最小值和最大值，添加新元素的时间复杂度为 O(log n)。

有一个最小堆和一个最大堆，用于保存数组的最后 n 个元素。这些元素需要是您稍后可以引用的节点。
有一个链表或任何数据结构形式的队列，其中 FIFO 操作具有恒定的时间复杂度。跟踪此队列中的最后 n 个元素。队列的每个元素都包含对最小和最大堆中相应条目的引用。
每当将新元素添加到数组时，请执行以下操作：

将其添加到最小和最大堆：log n 次操作。
在队列中查询对这个新元素的引用：常量操作。
从队列中取出n长度window元素的引用：常量操作。
从最小和最大堆中删除该元素：log n 操作。

最小堆和最大堆在恒定时间内随时为您提供最后 n 个元素的当前最小和最大元素。

虽然不会改变时间复杂度的一种可能的优化是将对堆的删除和添加操作合并到一个步骤中。您要做的是用新元素的值更新要从堆中删除的引用的值。然后运行对堆进行游泳和下沉操作以保持其不变性。然后您将再次将 dequed 引用放入队列中，因为它现在保存 n 长度 window.

中的最新值

Answer 3

谢谢大家。这是我对 Deque-based 算法的 Java 实现（


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;
        }
    }

}

序列中最后 N 个条目最大值的增量算法

Incremental algorithm for maximum of last N entries in a series

algorithm

max

min