連續固定長度子序列中的最大差值

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）。