c++ - 查找数字数组中最大差异的算法

Question

我有一个包含几百万个数字的数组。

double* const data = new double (3600000);

我需要遍历数组并找到范围(数组中的最大值减去最小值)。但是，有一个问题。我只想找到最小值和最大值在 1000 个样本内的范围。

所以我需要找到最大值:range(data + 0, data + 1000), range(data + 1, data + 1001), range(data + 2, data + 1002), ....,范围(数据 + 3599000，数据 + 3600000)。

我希望这是有道理的。基本上我可以像上面那样做，但是如果存在的话，我正在寻找一种更有效的算法。我觉得上面的算法是O(n)，但是我觉得可以优化。我正在玩的一个想法是跟踪最近的最大值和最小值以及它们有多远，然后仅在必要时回溯。

我将在 C++ 中对此进行编码，但是在伪代码中使用一个不错的算法就可以了。另外，如果我要查找的这个号码有名字，我很想知道它是什么。

谢谢。

Answer 1

这类问题属于称为流式算法的算法分支。它研究的问题不仅需要 O(n) 解决方案，还需要一次性处理数据。数据作为流输入到算法中，算法无法保存所有数据，然后永远丢失。算法需要得到一些关于数据的答案，例如最小值或中值。

具体来说，您正在寻找流上方窗口中的最大值(或更常见的文献中的最小值)。

Here's a presentation在 article提到这个问题是他们试图解决的问题的一个子问题。它可能会给你一些想法。

我认为解决方案的大纲是这样的——在流上维护窗口，在每个步骤中，一个元素被插入到窗口中，一个元素从另一侧移除(滑动窗口)。您实际保存在内存中的项目并不是窗口中的 1000 个项目的全部，而是选定的代表，它们将成为最小(或最大)的良好候选者。

阅读文章。它有点复杂，但经过 2-3 次阅读后，您就可以掌握它的窍门了。