Application of Link Lists

Introduction

這週我們要來學習如何使用串列來解決一些問題。

Sliding Window

Concept

有時候我們會遇到這樣的問題，問題希望你找出所有長度為 \(k\) 的連續區間的最大最小值。
這時候，我們可以使用滑動窗口的技巧完成這樣的問題。

滑動窗口主要關注元素的進出，以最大值為例，我們可以維護一個雙向佇列 (deque)。
這個 deque 裡面存放由大到小的元素位址。

以下表為例，假設 \(k=4\)。

陣列位址	1	2	3	4	5	6
陣列元素	5	2	4	-3	-1	9

則區間 \(1-4\) 的最大值為 \(5\)。
區間 \(2-5\) 則為 \(4\)，依此類推。

我們可以藉由對 doubly link list 的操作，處理每一個區間的最大值。

// 維護最大值 list
const int N = 100010;
int a[N];
List dq;

void op(int n, int k) {
    while (dq.front() < n - k) {
        dq.pop_front();
    }

    while (a[dq.back()] < a[n]) {
        dq.pop_back();
    }

    dq.push_back(n);
}

front 會存最大值的位址。只要重複這樣的步驟就可以完成對所有區間的最大值查詢。

Time Complexity

看到完整演算法的雙層迴圈我們可能會以為它的複雜度是 \(O(n^2)\)，
但其實不然，因為我們的元素最多就是進去還有出來 deque 一次。
所以平均的時間複雜度是 \(O(n)\)。

通常滑動窗口的技術都可以將複雜度下降，因為我們關注進出。這樣的想法在進階技術會再出現一次，也就是莫隊算法。
這一題我們也可以使用 priority_queue，不過時間複雜度會變為 \(O(n\log{(n)})\)。

Samples and Practices

最長不重複區間

題目敘述

給你一個長度為 \(n\) 的陣列，請求出最長的連續區間，使區間內任兩個數字都不相同。

輸入說明

第一行輸入一個數字 \(n\)。
第二行輸入 \(n\) 個數字，表示陣列本身。

輸出說明

輸出一個數字，表示滿足這樣的條件的區間長度。

範例測試

範例輸入 1

5
1 2 3 2 1	

範例輸出 1

3

範例輸入 2

7
1 5 3 4 2 5 2	

範例輸出 2

5

最小覆蓋子字串

題目敘述

給定一個字串 \(S\) 和一個字串 \(T\)，請在 \(S\) 中找出包含 \(T\) 所有字母的最小子字串。

輸入說明

第一行輸入一個字串 \(S\)。
第二行輸入一個字串 \(T\)。

輸出說明

請輸出最小所需長度。

範例測試

範例輸入 1

ADOBECODEBANC
ABC	

範例輸出 1

4