单链表
适用于邻接表：存储图和树
//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]];
}
双链表(暂时不写)
优化某些问题
栈
先进后出
int stk[N],tt;
//插入
stk[++tt] = x;
//弹出
tt--;
//判断栈是否为空
if(tt > 0) not empty
else empty
//栈顶
stk[tt];
单调栈
给定一个长度为N的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出-1。
输入格式
第一行包含整数N，表示数列长度。
第二行包含N个整数，表示整数数列。
输出格式
共一行，包含N个整数，其中第i个数表示第i个数的左边第一个比它小的数，如果不存在则输出-1。
数据范围
1≤N≤105
1≤数列中元素≤109
输入样例：
5
3 4 2 7 5
输出样例：
-1 3 -1 2 2
#include<iostream>
using namespace std;
const int N = 1e5+10;
int stk[N],tt;
int main(){
int n;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 ";
stk[++tt]=x;
}
}
队列
先进先出
//在队尾插入元素，在队头弹出元素
int q[N],hh,tt=-1;
//插入
q[++tt]=x;
//弹出
hh++;
//判断队列是否为空
if(hh <= tt) not empty
else empty
//取出队头元素
q[hh]
单调队列(滑动窗口)
给定一个大小为n≤106的数组。
有一个大小为k的滑动窗口，它从数组的最左边移动到最右边。
您只能在窗口中看到k个数字。
每次滑动窗口向右移动一个位置。
以下是一个例子：
该数组为[1 3 -1 -3 5 3 6 7]，k为3。
窗口位置 最小值 最大值
[1 3 -1] -3 5 3 6 7 -1 3
1 [3 -1 -3] 5 3 6 7 -3 3
1 3 [-1 -3 5] 3 6 7 -3 5
1 3 -1 [-3 5 3] 6 7 -3 5
1 3 -1 -3 [5 3 6] 7 3 6
1 3 -1 -3 5 [3 6 7] 3 7
您的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。
输入格式
输入包含两行。
第一行包含两个整数n和k，分别代表数组长度和滑动窗口的长度。
第二行有n个整数，代表数组的具体数值。
同行数据之间用空格隔开。
输出格式
输出包含两个。
第一行输出，从左至右，每个位置滑动窗口中的最小值。
第二行输出，从左至右，每个位置滑动窗口中的最大值。
输入样例：
8 3
1 3 -1 -3 5 3 6 7
输出样例：
-1 -3 -3 -3 3 3
3 3 5 5 6 7
#include<iostream>
using namespace std;
const int N = 1e6+10;
//用队列来存储当前数组的下标
int a[N],q[N],hh,tt=-1;
int n,k;
int main(){
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
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("");
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]]);
}
}