4

将序列的位移定义为最大和最小元素之间的差。给定一个整数序列，找出所有长度为 的连续子序列的最大位移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;
}
4

1 回答 1

3

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

计算线性时间的滑动最大值是一个标准问题，这里对不同的技术有很好的解释。如果链接中断，以下是该链接中线性时间算法的描述：

这里介绍的算法是升最小值算法；它需要 O(n) 时间和 O(k) 空间。一般的想法是在窗口中找到最小值，然后在窗口的其余部分中找到最小值，依此类推。可以忽略上升最小值之间的值。

更正式地说，令 W 是长度为 k 的值的向量。定义升序mimima A的序列如下：

令 A[0] 为 W 中的最小值，对于 j>0，令 A[j] 为 W 中的最小值，其索引大于 A[j-1] 的索引。（如果两个位置的最小值相同，则取后一个。）示例：

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

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

a：删除A中所有大于等于x的元素，

b：将 x 附加到 A，

c: 如果 A 的初始元素正在从窗口中移除，则移除它。

我们不需要记录窗口；我们所需要的只是升序的最小值序列。但是，需要记录何时从窗口中删除序列中的条目。出于这个原因，如果 A 的元素有两个字段，第一个是来自 V 的值，即某些 i 的 V[i]，第二个是条目将从窗口中消失时的索引，这是很有用的。这发生在 k 个条目之后。

由于 A 的长度是有界的，并且由于 A 是一个队列，所以很自然地将它存储在一个环形缓冲区中。

步骤 (b) 和 (c) 很简单，没有重要的替代方案。在步骤 (a) 中，我们需要找到 A 中小于新添加的 x 的最后一个值。乍一看，A 的二分搜索似乎是最优的。不是这种情况; 最佳搜索是在一个简单的循环中从后到前。

证明很简单；线性搜索循环一个一个地删除元素，每次删除的时间成本为 O(1)。平均而言，从 A 中删除的次数与添加的次数相同。结果是将窗口移动一个位置的平均时间成本为 O(1)。

于 2014-12-05T10:41:20.620 回答