HDU 3530 單調隊列尋找最長子序列

題目大意

給定一個數列，尋找最長的連續子序列，使得該子序列中最大值與最小值的差值在 [m, k] 範圍內。

解法：雙單調隊列

維護兩個單調隊列：一個單調遞增（用於獲取區間最小值），一個單調遞減（用於獲取區間最大值）。雙指針滑動窗口，右端點不斷擴展，左端點根據條件收縮。

關鍵步驟

1. 新元素入隊時，維護單調性：遞增隊列彈出尾部大於等於新值的元素；遞減隊列彈出尾部小於等於新值的元素。
2. 檢查隊首元素對應的最大值與最小值之差是否超過 k。若超過，移動左指針：比較兩隊隊首的索引，拋棄索引較小的那一側，並更新左邊界。
3. 當差值 ≥ m 時，更新答案為當前窗口長度。

代碼精要

while (ma[fax+1] - mi[fin+1] > k && fax < tax && fin < tin) {
    if (ida[fax+1] <= idi[fin+1]) { fax++; now = ida[fax]; }
    else { fin++; now = idi[fin]; }
}
if (ma[fax+1] - mi[fin+1] >= m) ans = max(ans, i - now);

複雜度

每個元素最多入隊出隊一次，時間 O(n)，空間 O(n)。

總結

雙單調隊列是解決滑動窗口最大/最小值問題的利器，配合雙指針可高效處理區間約束條件。