连续固定长度子序列中的最大差值

Question

将序列的位移定义为最大和最小元素之间的差值。给定一个整数序列，找到长度为m的所有连续子序列的最大位移。

例如，如果我们的序列为[1，5，7，0,2，-4]且m = 3，

• [1，5,7]的位移6.
• [5,7，0]具有位移7.
• [7,0，2]具有位移7.
• [0，2，-4]具有位移6.
• 所以最大位移为7。

如果我们让n表示输入序列的长度，那么我的解决方案在O（nlog（m））时间内运行。有什么办法可以做得更好吗？我觉得必须有我缺少的线性时间算法。 就这个问题而言，我关心的只是渐近时间复杂度。

#include <vector> 
#include <set> 
#include <iostream> 
int find_max_displacement(std::vector<int> seq, int m){ 
    std::multiset<int> subseq; 
    // insert the m items of first subsequence into tree 
    for (int i = 0; i < m; i++){ 
     subseq.insert(seq[i]); 
    } 
    int max_disp = *subseq.rbegin() - *subseq.begin(); // max minus min 
    for (int i = 0; i < seq.size() - m; i++){ 
     subseq.erase(subseq.find(seq[i])); // kick oldest element out of subsequence 
     subseq.insert(seq[i+m]);   // insert new element into subsequence 
     int new_disp = *subseq.rbegin() - *subseq.begin(); 
     if (new_disp > max_disp){ 
      max_disp = new_disp; 
     } 
    } 
    return max_disp; 
} 
int main(){ 
    std::vector<int> arr {1, 5, 7, 0, 2, -4}; 
    int max_disp = find_max_displacement(arr, 3); 
    std::cout << max_disp << std::endl; 
    return 0; 
} 

Answer 1

你说得对，这里有一个线性时间算法。您可以使用滑动最大值和最小滑动数组来计算数组，并找出这两个数组之间的最大差异。

在线性时间内计算滑动最大值是一个标准问题，对不同的技术here有很好的解释。在情况下，链接场所，这里是线性时间算法的从该链接的描述：

这里提出的算法是上升极小算法;它 需要O（n）时间和O（k）空间。总体思路是在窗口中查找最小值 ，然后在 窗口的其余部分查找最小值，等等。升序最小值之间的值可以忽略。

更正式地说，设W是长度为k的向量。限定升序mimima，A的 序列，如下所示：

让在W和对于j A [0]是最小值> 0让A [j]的单位为W是最小 值与指数比大于A [j-1]的索引。 （如果两个 位置具有相同的最小值取的后一个。）实施例：

W = 5,2,8,6,4,7 
A = 2,4,7 

显然A的长度为1，如果 最小值W是在W和k中的最后一个元素，如果W为单调 增加。现在假设我们在V上有一个窗口W，并且我们知道上升的最小向量A。考虑当我们将 窗口移动到一个位置时会发生什么。我们在窗口的末尾添加一个元素，并从窗口的开头删除一个元素。设x是 新添加的元素。然后A可以通过

更新的：除去大于或等于x，

B的所有元素：附加x到A，

C：和拆卸的，如果它的初始元件正从窗口中移除。

我们不需要记录窗口;我们所需要的只是 递增最小序列。但是，有必要记录序列中的 条目何时将从窗口中删除。由于这个原因 它是有用的，如果A的元素有两个字段，第一个是从V的 值，即V [i]对于某些我和第二个是索引 当条目将从窗口消失。此后发生k个条目 。

由于A的长度是有界的，并且由于A是队列，因此将它存储在环形缓冲区中是很自然的。 （b）和（c）是直接的，没有显着的 替代方案。在步骤（a）中，我们需要定位A中的最后一个值，即 小于新添加的x。乍一看，似乎A的二元搜索将是最优的。不是这种情况;最佳的 搜索是从一个简单的循环回到前面。

证明很简单;线性搜索循环以每个删除的O（1）时间成本逐个删除元素 。平均来说，A的删除数量与添加的数量相同。结果 的结果是移动窗口的一个位置 的平均时间成本是O（1）。