链表
- 我们这里不用结构体+指针来实现链表,而是用数组来模拟,因为这样效率高。普通题目中一般有上万个结点,每个节点执行一个new操作太慢了,所以不用结构体+指针这种方式。
单链表(邻接表:存储图和数)
- 每个节点都有两个属性:value和next指针,我们分别将所有节点的value存到e[N]数组,将所有节点的next指针存到ne[N]数组,这两个数组通过下标进行关联
单链表的常用操作:
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
// head 表示头结点的下标
// e[i] 表示结点i的值
// ne[i] 表示结点i的next指针是多少(结点i的下一个节点的下标是什么)
// idx 存储当前已经用到了哪个点
int head, e[N], ne[N], idx;
void init() //初始化
{
head = -1; //头节点指向空(链表是空的)
idx = 0; //当前可以从0号点开始用
}
//将x插入到头结点
void add_to_head(int x)
{
e[idx] = x; //把这个值存下来
ne[idx] = head; //给这个结点赋next下标值
//此处的head指向第一个结点,即head存的就是第一个结点(头结点)的下标
//head赋给ne[idx]就是把原来的首节点下标赋给这个插入的新节点的下一个节点的下标
head = idx; //此时x变成了第一个结点,所以head指向它,即head存它的下标
idx++; //当前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]]; //直接跳过要删除的那个结点指向它后面的结点
}
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
// head 表示头结点的下标
// e[i] 表示结点i的值
// ne[i] 表示结点i的next指针是多少(结点i的下一个节点的下标是什么)
// idx 存储当前已经用到了哪个点
int head, e[N], ne[N], idx;
void init() //初始化
{
head = -1; //头节点指向空(链表是空的)
idx = 0; //当前可以从0号点开始用
}
//将x插入到头结点
void add_to_head(int x)
{
e[idx] = x; //把这个值存下来
ne[idx] = head; //给这个结点赋next下标值
//此处的head指向第一个结点,即head存的就是第一个结点(头结点)的下标
//head赋给ne[idx]就是把原来的首节点下标赋给这个插入的新节点的下一个节点的下标
head = idx; //此时x变成了第一个结点,所以head指向它,即head存它的下标
idx++; //当前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 main()
{
int m;
cin>>m;
init(); //初始化
while(m--)
{
int k,x;
char op;
cin>>op;
if(op=='H')
{
cin>>x;
add_to_head(x);
}
else if(op == 'D')
{
cin>>k;
if(k==0) head = ne[head]; //k=0,删除头结点
else remove(k-1); //第k个点的下标是k-1
}
else
{
cin>>k>>x;
add(k-1,x); //第k个点的下标是k-1
}
}
for(int i = head;i!=-1;i = ne[i]) cout<<e[i]<<' ';
cout<<endl;
return 0;
}
双链表 (优化某些问题)
- 与单链表每个结点只有一个指针ne[i]不同,双链表每个结点有两个指针l[i],r[i],分别存储这个结点前面和后面的结点的下标。
双链表的常用操作:
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int m;
int e[N],l[N],r[N],idx;
//初始化
void init()
{
//不设置头尾指针head和tail,偷个懒
//用下标0表示左端点,1表示右端点
//一开始双链表是空的时候,0号点右边是1号点,1号点左边是0号点
r[0] = 1;
l[1] = 0;
idx = 2; //以后的结点下标从2开始用,因为0和1已经被占用过了
}
//在下标为k的点的右边插入x
void add(int k, int x)
{
e[idx] = x;
r[idx] = r[k];
l[idx] = k;
l[r[k]] = idx; //一定要先调用l[r[k]]再修改r[k],最后两行顺序不能反
r[k] = idx;
idx++;
}
//当想在下标为k的点的左边插入一个点,可以在直接调用add(l[k],x)
//即在k左边的点的右边插入点x,等价于在k的左边插入点x
//删除下标为k的点
void remove(int k)
{
r[l[k]] = r[k]; //让k的左边的右边直接等于k的右边
l[r[k]] = l[k]; //让k的右边的左边直接等于k的左边
}
栈与队列
栈与队列的常用操作
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
// **********************************栈
int stk[N]; //栈stack
int tt; //栈顶下标
//入栈一个新的元素
stk[++tt] = x;
//弹出
tt--;
//判断栈是否为空
if(tt>0) //不空
else //空
//栈顶元素
stk[tt];
// **********************************队列
int q[N]; //queue,队列
int hh; //队头,弹出元素
int tt = -1; //队尾,插入元素
//插入
q[++tt] = x;
//弹出
hh++; //队头指针往后移动一位就是弹出队头的元素
//判断是否为空
if(hh<=tt) //队头<队尾,非空
else //队头在队尾后面,空
//取出队头元素
q[hh];
单调栈与单调队列:
- 单调栈和单调队列的思路与双指针算法类似:先思考暴力解法,再从中发现一些单调性,利用单调性对问题作出优化
单调栈的应用:
-
找到某个数左边离他最近的比他小的数
-
首先思考暴力做法:i枚举数组,j每次从i-1开始往前走,找到第一个比a[i]小的数则停止。时间复杂度O(n^2)
- 用一个栈维护i左边的数,我们可以发现,当出现逆序对的时候,比如x 5 x 3 x……,这种情况下5是不可能被用到的,因为我们要找的是离a[i]左边最近的小于a[i]的数,那如果5是满足小于a[i]的,那3一定也小于a[i]啊,而且3离得近,所以5的右边有小于5的数的时候(逆序对),5是不可能被用上的,可以剔除。
- 这样操作之后,我们维护的这个栈就是一个单调递增的栈。每次找比a[i]小的值就找到第一个就是最近的。
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int stk[N];
int tt;
int n;
int main()
{
cin>>n;
for(int i = 0;i<n;i++)
{
int x;
cin>>x;
//栈非空且栈顶元素不小于当前元素,弹出栈顶元素
//下一次循环的时候x会入栈,即使之前大于x的元素都被弹出来了也不影响求出正确答案
//比如x=2,栈内的4被弹出来了,那么下一次,x=7,要找最近的小于7的数,
//是不会考虑4的,因为2满足比7小且2之于7的距离比4之于7近,所以4出栈了无所谓
// 所以栈内的元素始终会是单调递增的序列
while(tt && stk[tt]>=x ) tt--;
//直到栈空或者找到一个小于当前元素x的元素跳出while循环
//如果是因为找到小于x的元素跳出的while,即栈非空,则输出栈顶元素
//此时栈顶元素就是我们要找的最近的小于x的元素
if(tt) cout<<stk[tt]<<' ';
//如果是因为栈空跳出的while,即没找到小于x的元素,输出-1
else cout<<-1<<' ';
//把当前这个元素入栈,继续 循环讨论下一个元素
stk[++tt] = x;
}
return 0;
}
单调队列的应用:
- 求滑动窗口里的最大值和最小值
滑动窗口:原题链接
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n,k;
int a[N];
int q[N]; //求最小值时是单调递增队列,求最大值时是单调递减序列
int main()
{
scanf("%d%d", &n, &k);
for(int i = 0;i<n;i++) scanf("%d", &a[i]);
int hh = 0; //队头
int tt = -1; //队尾
for(int i = 0;i<n;i++)
{
//维持滑动窗口的大小,若队头滑出了窗口,则hh++
//hh<=tt 代表队列非空
//队列里存的是数字在原数组中的下标
//当前窗口终点下标是i,那么起点就是i-k+1,若队头q[hh]小于这个起点,说明滑出窗口了,需要hh++
//q[hh]存的是窗口左端位置(队头)的元素在原数组的下标。
if(hh<=tt && i-q[hh]+1 > k) hh++;
//构造单调队列
//当队列不为空,且当队列队尾元素>=当前元素a[i]时,
//这个队尾元素在之后都不会作为最小值输出,因为a[i]比他小且比他晚出窗口
//所以这个队尾元素就一定不是当前窗口的最小值,删去队尾元素,加入当前元素
while (hh<=tt && a[q[tt]] >= a[i]) tt--;
q[++tt] = i;
//队列中从左到右是递增的,即最后输出队头的就是最小的
//i>=k-1代表窗口里有三个元素,比如到第二个数时,i=1,窗口里都没有3个数
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-q[hh]+1 > k) hh++;
while (hh<=tt && a[q[tt]] <= a[i]) tt--;
q[++tt] = i;
if(i>=k-1) printf("%d ",a[q[hh]]);
}
return 0;
}