數組模擬（二）

• 2021 年 10 月 24 日
• 筆記
• 知識點

數組模擬（二）

單調棧

給定一個長度為 N 的整數數列，輸出每個數左邊第一個比它小的數，如果不存在則輸出 −1。

因為每一個答案（左邊比它小的數）只跟局部的最小值相關，即左邊第一個比它小的值

如果出現一個比較小的值（比前面的數小），則前面的數對於後面數的答案是無效的

所以我們可以用單調棧來實現，用棧來維護一個單調遞增的數列即可，遇見較小值則清空

int stk[N], tt; // 模擬棧，tt為棧頂
cin >> n;// 數列個數
while(n --)
{
    int x;
    cin >> x;
    // tt：棧非空 stk[tt] >= x 遇見了較小值
    while(tt && stk[tt] >= x) tt --; // 出棧
    if(!tt) printf("-1") // 棧為空則不存在比它小的值，都在上一步出完了
    else cout << stk[tt];// 否則棧頂即為比當前數小的第一個值
    stk[++tt] = x; // 把這個數入棧，此時棧內一定是單增的，簡單理解請自行思考
}

單調隊列

滑動窗口

確定滑動窗口位於每個位置時，窗口中的最大值和最小值

int a[N]; // 存儲數列
int q[N], tt = -1, hh; // 模擬隊列, q存儲數列下標

int main()
{
    int n, k;
    cin >> n >> k; // 數列長度， 窗口長度
    for(int i = 0; i < n; i ++) cin >> a[i];
    
    // 先求最小值
    for (int i = 0; i < n; i ++)
    {
        if (i - k + 1 > q[hh]) hh ++; // 隊頭出滑動窗口，則更新隊頭
        while (hh <= tt && a[q[tt]] >= a[i]) tt --; // 遇見較小值， 出隊
        q[++tt] = i; // 滑動窗口滑動時，輸出值可能是剛剛進來的，所以這裡要先入隊
        
        // 輸出隊頭元素即可，維護的是一個單增序列
        if(i >= k - 1) cout << a[q[hh]] << ' '; // i < k - 1時窗口放不下
    }
    
    cout << endl;
    // 求最大值同理, 但要記得重置
    tt = -1, hh = 0;
    for (int i = 0; i < n; i ++)
    {
        if (i - k + 1 > q[hh]) hh ++;
        while (hh <= tt && a[q[tt]] <= a[i]) tt--;
        q[++tt] = i;
        
        if(i >= k - 1) cout << a[q[hh]] << ' ';
    }
    return 0;
    
}

KMP字元串匹配問題

 #include <iostream>

using namespace std;
const int N = 100010, M = 1000010;
int n, m; 
int ne[N]; // KMP核心next數組
char s[M], p[N]; // s為字元串原串，p為匹配串
int main()
{
    // 字元串從1開始
    cin >> n >> p + 1 >> m >> s + 1;
    
    for (int i = 2, j = 0; i <= n; i ++)
    {
        // j為0或者不相等時找到上一個j(p[j]的位置)
        while (j && p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1]) j ++; // 當前字元匹配成功時匹配下一個
        ne[i] = j; // 取得最長公共子串的值
    }
    
    for (int i = 1, j = 0; i <= m; i ++)
    {
        // 不等於模式串就返回上一個相同前綴的坐標
        while (j && s[i] != p[j + 1]) j = ne[j];
        if(s[i] == p[j + 1]) j ++; // 匹配成功一個字元
        if (j == n) // 匹配成功輸出成功匹配的起始坐標，繼續匹配下一個
        {
            printf("%d ", i - n);
            j = ne[j];
        }
    }
    return 0;
}