c++ - 连续固定长度子序列的最大差异

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 .万一链接断开，这里是来自该链接的线性时间算法的描述:

The algorithm presented here is the ascending minima algorithm; it requires O(n) time and O(k) space. The general idea is to locate the minimum in the window, then the minimum in the remainder of the window, and so. Values between the ascending minima can be ignored.

More formally, let W be a vector of values of length k. Define the sequence of ascending mimima, A, as follows:

Let A[0] be the minimum value in W and for j>0 let A[j] be the minimum value in W with index greater than the index of A[j-1]. (If two locations have the same minimum value take the later one.) Example:

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

Evidently the length of A is 1 if the minimum in W is the last element in W and k if W is monotonic increasing. Now suppose that we have a window W on V and that we know the ascending minima vector A. Consider what happens when we move the window one location. We add one element at the end of the window and remove one element from the beginning of the window. Let x be the newly added element. Then A can be updated by

a: removing all elements of A greater than or equal to x,

b: appending x to A,

c: and removing the initial element of A if it is being removed from the window.

We do not need to record the window; all we need is the ascending minima sequence. However it is necessary to record when an entry in the sequence will be deleted from the window. For this reason it is useful if the elements of A have two fields, the first being a value from V, i.e., V[i] for some i, and the second being the index when the entry will disappear from the window. This happens k entries later.

Since the length of A is bounded and since A is a queue, it is natural to store it in a ring buffer.

Steps (b) and (c) are straightforward without significant alternatives. In step (a) we need to locate the last value in A that is less than the newly added x. At first sight it might seem that a binary search of A would be optimal. This is not the case; the optimal search is from back to front in a simple loop.

The proof is simple enough; the linear search loop deletes elements one by one with an O(1) time cost for each deletion. On average the number of deletions from A is the same as the number of additions. The upshot is that the average time cost of moving the window one location is O(1).