数组模拟（二）

单调栈

给定一个长度为 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;
}