数据结构

（数组模拟，用静态链表而不是动态链表是因为其效率相对较高）

链表与邻接表

单链表·（邻接表：存储图和树）

首先用数组e[n]表示某点的值，ne[n]表示某点的next指针，二者靠下标关联，空节点下标设为-1


//值      3    5    7    9
head -> O -> O -> O -> O -> 空节点
//下标    0    1    2    3      -1

e[0] = 3,  e[1] = 5, e[2] = 7, e[3] = 9
en[0] = 1,ne[1] = 2,ne[2] = 3,ne[3] = -1

const int N = 100010;

//head表示头节点的下标
//e[i]表示节点i的值
//ne[i]表示节点i的next指针
//idx 储存当前已经用到了哪个点
int head,e[N],ne[N],idx;

//初始化
void init(){

    head = -1;
    idx = 0;
}

//将x插到头节点
void add_to_head(int x){
    e[idx] = x;
    ne[idx] = head
    head = idx;
    idx ++;
}

//将x插入到下标是k的节点
void add(int k,int x){
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx ++;
}

//将下标是k的点的后面节点删去
void remove(int k){
    ne[k] = ne[ne[k]];
}

双链表

此处用下标是0的点代表头节点，下标是1的点代表尾节点

//l[N]和r[N]分别是指向左右的指针

int m;
int e[N],l[N],r[N],idx;

//初始化
void init(){
    //0表示左端点，1表示右端点
    r[0] = 1;l[1] = 0;
    idx = 2;
}

//在下标是k的点的右边插入x
void add(int k,int x){

    e[idx] = x;
    r[idx] = r[k];
    l[idx] = k;
    l[r[k]]  = idx;
    r[k] = idx;

}

//若在左边插入，可用
add(l[k]);

//删除第k个点

void remove(int k){
    r[l[k]] = r[k];
    l[r[k]] = l[k];

}

栈和队列

栈：先进后出 FILO(first in last out)
队列：先进先出 FIFO(first in first out)

栈

数组模拟栈十分简单

const int = 10010;

int stk[k],tt;//tt为栈顶 初始为0或1

//插入
stk[++ tt] = x;

//弹出
tt --

//判断栈是否为空
if(tt > 0) not empty
else empty

//栈顶
stk[tt]

队列

//在队尾插入元素，在队头弹出元素

int q[N],hh,tt = -1; //hh是队头，tt队尾

//插入
q[++ tt] = x;

//弹出
hh ++

//判空

if(hh <= tt) not empty
else empty

//取出队头元素
q[hh]

单调栈和单调队列

单调栈

单调栈的应用场景较少，可以看如下的例题

例：


给定一个长度为 N的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1

第一行包含整数 N，表示数列长度。

第二行包含 N 个整数，表示整数数列。

该题若使用暴力做法做的话用双重循环

用一个栈存储i左边的所有元素，i指针每往右移动一位就往栈里加入一个新的数
经过观察可知，一些元素永远不会输出，如a~3~ >= a~5~,则a~3~一定不会被输出

即若a~x~ >= a~y~ 且 x < y 则a~x~可以被删掉，剩下的序列一定是严格单调上升序列

代码实现：


const int N = 10010;
int n;
int stk[N],tt;

int main(){

    ios::sync_with_stdio(false);//

    cin >> n;

    for(int i = 0;i < n;i ++){
        int x;
        cin >> x;
        while(tt && stk[tt] >= x) tt --;
        if(tt) cout << stk[tt] <<" ";
        else cout << -1 << endl;

        stk[++ tt] = x;

    }
    return 0;
}

单调队列

例：

滑动窗口


给定一个大小为 n≤10^6的数组组。

有一个大小为 k的滑动窗口，它从数组的最左边移动到最右边。

你只能在窗口中看到 k个数字。

每次滑动窗口向右移动一个位置。

你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。

窗口使用队列来维护，使用暴力做法就是遍历队列里的所有元素
可以考虑优化这个问题，例如在找最小值时窗口中有3，-1，-3，那么3比-3小且在-3左边，那么一定不会被输出，则3可以删去。同理-1也可以删去

即只要在该队列里前面有一个数比后面的数大，就可将其删掉。强所有的逆序对全部删掉，这个队列就会变成严格单调上升序列

此时求其最小值只需找到队头

题解：

const itn N = 1000010;

int n;
int a[N],q[N];//q中存储的是下标

int main(){
    scanf("%d",&n);
    for(int i = 0;i < n;i ++) scanf("%d",&a[i]);

    int hh = 0;tt = -1;
    for(int i = 0;i < n;i ++){
        //判断队头是否已经滑出窗口
        if(hh <= tt && i - k + 1 > q[hh]) hh++;
        while(hh <= tt && a[q[tt]] >= a[i]) tt--;
        q[++ tt] = i;
        if(i >= k - 1) printf("%d",a[q[hh]]);
        puts("");
    }

    int hh = 0;tt = -1;
    for(int i = 0;i < n;i ++){
        //判断队头是否已经滑出窗口
        if(hh <= tt && i - k + 1 > q[hh]) hh++;
        while(hh <= tt && a[q[tt]] <= a[i]) tt--;
        q[++ tt] = i;
        if(i >= k - 1) printf("%d",a[q[hh]]);
        puts("");
        return 0;
    }
}

kmp

KMP算法要解决的问题就是在字符串（也叫主串）中的模式（pattern）定位问题。说简单点就是我们平时常说的关键字搜索。模式串就是关键字，如果它在一个主串中出现，就返回它的具体位置，否则返回-1（常用手段）。

若使用暴力做法，则从主串的第i个位置为起点，与模式串逐个比较，若出现不匹配，就将起点i往后移动一位

Alg-learn