链表分为动态链表和静态链表 动态链表如下 :
struct Node{ int val ; Node *next ; }但由于 在 c++ 中,在使用动态链表的情况下,每次创建一个链表就需要调用 new() 函数来创建为其创建一个空间进行存储,但是据我们所知 , c++ 中的new()函数是非常慢的, 当我们处理百万级以上的数据时,使用动态链表就会超时,注意 : 这里所说的情况仅仅只针对于算法题中, 不考虑内存泄露的问题,而在实际的工程项目中,需要考虑内存的问题.
所以在算法题中我们常常用 数组 来模拟链表 , 也就是我们所说的静态链表.
模版 : H 表示向头结点插入一个结点 I 表示向 k - 1 的结点后面插入一个结点 D 表示删除第 k - 1 个结点后面的结点
// 数组实现单链表 -- 静态链表 #include <iostream> using namespace std; const int N = 100010 ; int head , e[N] , ne[N] , idx ; // 初始化操作 void init() { head = -1 ; idx = 0 ; } // 插入到头结点 void add_to_head(int x) { e[idx] = x ; ne[idx] = head ; head = idx ++ ; } // 将 x 插入到下标为 k 的结点的后面 k - 1 void add(int x, int k) { e[idx] = x ; ne[idx] = ne[k] ; ne[k] = idx ++ ; } // 将下标为 k 的结点的后面的点删掉 void remove(int k) { ne[k] = ne[ne[k]] ; } int main() { int n ; cin >> n ; init() ; while(n -- ) { int k , x; char op ; cin >> op ; if(op == 'H') { cin >> x; add_to_head(x) ; } else if(op == 'D') { cin >> k; if(!k) head = ne[head] ; remove(k - 1) ; // 注意因为下标从零开始 删除第k个数后面的数是删 下标 k-1后面的 数 } else { cin >> k >> x; add(x , k - 1) ; // 与上面删除操作同理 所以这里传参的时候需要 - 1 } } for(int i = head ; i != - 1;i = ne[i]) cout << e[i] << " " ; return 0; }每个结点有两个指向 分别指向前面或者后面 这样在进行插入操作的时候就可以对前后进行插入 且时间复杂度为 O( 1 )
模版 :
#include <iostream> using namespace std; const int N = 100010 ; int e[N] , l[N] , r[N] , idx ; void init() { r[0] = 1; l[1] = 0; idx = 2; } // 在第 k 个点的后面插入一个点 void add(int k,int x) { e[idx] = x; r[idx] = r[k] ; l[idx] = k ; // 这里要注意修改结点指向的先后顺序 !!! l[r[k]] = idx ; r[k] = idx ; } // 删除第k个点 void remove(int k) { l[r[k]] = l[k] ; r[l[k]] = r[k]; }部分代码 :
#include <iostream> using namespace std; const int N = 100010 ; int e[N] , l[N] , r[N] , idx ; void init() { r[0] = 1; l[1] = 0; idx = 2; } // 在第 k 个点的后面插入一个点 void add(int k,int x) { e[idx] = x; r[idx] = r[k] ; l[idx] = k ; // 这里要注意修改结点指向的先后顺序 !!! l[r[k]] = idx ; r[k] = idx ; } // 删除第k个点 void remove(int k) { l[r[k]] = l[k] ; r[l[k]] = r[k]; }应用 : 给定一个序列 . 求这个序列中的每一个数左边离他最近的且比它小的数 , 没有的话则返回 -1
思路 : 这里考虑的方法与双指针算法考虑类似 , 首先暴力求解 , 再挖掘一些性质使得我们可以把 焦点 集中在比较少的状态里面 --> 时间复杂度降低
在这个问题中, 首先我们假设这里有一个数轴 , 它是从 a1 — ai 那么我们要求 离ai 最近且比 ai小的数 从暴力入手 , 可得到如下代码 :
for (int i = 0;i < n;i ++ ) for(int j = i -1;j >= 0;j -- ) if(ai > aj) { cout << aj << endl; break ; }由此可见其时间复杂度为 O( n ) 此时我们可以把 ai 单独拎出来 , 剩下的 a1 – a(i-1)可以看作一个栈 , 通过观察我们可以发现如下性质 , 当ax >= ay 且 x < y 的时候,此时可以把 x 直接从栈中剔除 ,因为我们要找的是离ai最近且比ai小的元素,在这种情况下, ax不满足条件, 所以不需要进行比较 . 也就是说, 我们可以把 a1 ---- ai中所有逆序的点全部删掉 , 得到的就是一个单调栈 , 此时再从栈顶往下遍历这个栈并将其与 ai进行比较 , 如果 其 < ai 就可知其是正确答案 , 反之则知无正确答案 , 输出 - 1.
经过优化后整个算法的时间复杂度为 O( n )
代码如下:
#include <iostream> using namespace std; const int N = 100010 ; 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 ; // 当skt[tt] >= x 时, 栈顶元素弹出 直到 skt[tt] < x 或者 栈空 while(tt && stk[tt] >= x) tt -- ; if(tt) cout << stk[tt] << " " ; else cout << -1 << " " ; // 每次输入后 将 x 压入栈 等于在数轴的右边插入 x stk[++ tt] = x ; } return 0 ; }滑动窗口 :
给定一个数组 , 一个给定长度的滑动的窗口从其左边往右滑动 , 求每次滑动一个单位后 窗口 内的最值
思路 : 和单调栈一样 先想朴素算法如何实现 , 再从中挖掘一些性质 , 使得能把其中无用的元素剔除 , 从会儿实现优化 . 暴力做法 , 两重循环 , 每次向队列入队一个新元素的时候都需要添加循环一遍队列 , 这样复杂度非常大 , 很容易超时 . 优化方法 : 假设我们要求窗口中的最小值 , 例如这组数
3 -1 -3
很明显其最小值是 -3 , 而且-3在最右边 , 也就是队列的队尾,此时前面两个数都比其大 , 说明这两个数就不需要比较, 只要 -3 在 , 它们就永远都不可能输出 , 所以这两个数都可以删除 , 因此 , 我们可以得到 : 只要我们将比新插入的数大的数删去 , 最后就可以得到一个单调递增的队列, 由此可知 此时 队列的最小值即是队头所对应的值.(注: 在这里我们队列存的是数组的下标 , 而不是数组的值 .)
代码如下 :
// 单调队列 滑动窗口应用 // monotone queue #include <iostream> using namespace std; const int N = 1000010 ; int n , k; int a[N] , q[N] ; int main() { scanf("%d%d",&n,&k) ; 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 -- ; // 将当前插入的点 入队 // 这里是从 0 开始存队列中的数 所以前面计算起点的时候需要加一 q[++ tt] = i; // 输出 这里需要进行一层判断 只有窗口中的数大于等于 k 时才输出 if(i - k + 1 >= 0) printf("%d ",a[q[hh]]) ; } cout << endl ; // 求滑动窗口的最大值 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; // 输出 这里需要进行一层判断 只有窗口中的数大于等于 k 时才输出 if(i - k + 1 >= 0) printf("%d ",a[q[hh]]) ; } return 0 ; }