一：单链表

知识笔记：
image.png
笔试题一般是不会使用，原因是new的操作非常耗时，一般笔试题需要new十万或者百万级别的数据，当这些数据new完的时候，基本就已经超时。
image.png

e[N]代表了结点的值，ne[N]代表了当前结点指向的下一个结点。

把一个结点插入到头节点的地方，算法百分之八十都是插入到头结点的地方。
image.png
image.png

  1. #include <iostream>
  3. using namespace std;
  5. const int N = 1e5 + 10;
  6. int m;
  7. int e[N], ne[N], idx, head;
  10. // 总是忘记main中执行当前函数
  11. void init() {
  12.     head = -1;
  13.     idx = 0;
  14. }
  16. void insert(int x) { //头插法
  17.     e[idx] = x, ne[idx] = head, head = idx++; // 利用了逗号的运算符，本质就是上面的红色的过程，指向头节点，然后头节点指向这个新的结点
  18. }
  19. void add(int x, int c) { // 在指定位置插入，这里我感觉要是把头节点作为单独结点，也就是0作为头结点，就能合并两个函数。
  20.     e[idx] = c, ne[idx] = ne[x], ne[x] = idx++; // 和上面的插入函数很相似
  21. }
  23. void remove(int x) {
  24.     ne[x] = ne[ne[x]];
  25. }
  26. int main() {
  27.     cin >> m;
  28.     init();
  29.     while (m--) {
  30.         char op;
  31.         int x, c;
  32.         cin >> op;
  33.         if (op == 'H') {
  34.             cin >> x;
  35.             insert(x);
  36.         } else if (op == 'I') {
  37.             cin >> x >> c;
  38.             add(x - 1, c); // 为什么是x - 1?首先idx是0，题目说的很清楚，输入的是5，就是在第五个后面插入，所以需要在第四个后面插入内容
  39.         } else {
  40.             cin >> x;
  41.             if (x == 0) head  = ne[head]; // 因为删除的时候需要针对头节点做一个判断
  42.             remove(x - 1);
  43.         }
  44.     }
  45.     for (int i = head; i != -1; i = ne[i]) {
  46.         cout << e[i] << " ";
  47.     }
  48.     return 0;
  49. }

二：双链表

  1. #include <iostream>
  3. using namespace std;
  5. const int N = 1e5 + 10;
  6. int e[N], l[N], r[N], idx;
  8. void init() {　／／默认０作为头节点，１作为尾结点
  9.     r[0] = 1;
  10.     l[1] = 0;
  11.     idx = 2;　／／　ｉｄｘ从２开始代表后面删除和插入的时候都需要＋２
  12. }
  13. void insert(int x, int c) {
  14.     e[idx] = c;
  15.     r[idx] = r[x];
  16.     l[idx] = l[r[x]];
  17.     l[r[x]] = idx;
  18.     r[x] = idx;
  19.     idx ++;
  20. }
  21. void del(int x) {
  22.     l[r[x]] = l[x];
  23.     r[l[x]] = r[x];
  24. }
  26. int main() {
  28.     int m;
  29.     ios::sync_with_stdio(false);
  30.     cin >> m;
  31.     init();
  32.     while (m--) {
  33.         string op;
  34.         int x, c;
  35.         cin >> op;
  36.         if (op == "R") {ｓ
  37.             cin >> x;
  38.             insert(l[1], x);　／／　全都利用插入函数，尾部插入，需要找到尾结点的左边结点
  39.         } else if (op == "L") {
  40.             cin >> x;
  41.             insert(0, x);
  42.         } else if (op == "D") {
  43.             cin >> x;
  44.             del(x + 1);　／／理解上面的单链表，＋２然后　－１
  45.         } else if (op == "IL") {
  46.             cin >> x >> c;
  47.             insert(l[x + 1], c);／／这里不要误会，为什么不是ｘ，因为题目说了就是要插入第ｋ个数的左边，插入的时候肯定
  48.                 ／／是按照数组坐标的一个一个加，一个一个存储的，但是两个相邻的却不一定是链表结构上的相邻，座椅不能单纯用ｘ＋２－１，这样错误。
  49.         } else {
  50.             cin >> x >> c;
  51.             insert(x + 1, c);
  52.         }
  53.     }
  54.     for (int i = r[0]; i != 1; i = r[i]) 
  55.         cout << e[i] << " ";
  56.     return 0;
  57. }

三：单调栈

优化的本质就是删除没有用的，你比如5，6，3，4，当你找距离4，输出距离最近的小于等于4的数，5， 6其实是没有存在的必要的，这也是单调栈优化的点，while(tt && a[tt] >= x) tt—;就是删除前面比当前x大的数，这样的过程就是实现时间复杂度降低的过程。
image.png
image.png
image.png
y总的栈0相当于-1，实际的存储是从1开始存储的。
单调栈的应用实际上比较少，这个题的应用，实际上就是把每次输入都存入一个栈中，存入的时候有讲究，必须时按照顺序递增的方式存储，形成的栈一定是一个单调的栈，这里从底向上时递增的，出现不是递增的直接从栈中弹出。

  • 注意存入栈的顺序和队列是不一样的，下面滑动窗口那里是在输出的前面存入。 ```cpp

    include

using namespace std;

const int N = 1e5 + 10; int a[N], tt; int main() { int n; ios::sync_with_stdio(false); cin >> n; while (n—) { int x; cin >> x; while (tt && a[tt] >= x) tt—; //保证栈中是一个单调的序列，只要栈顶元素大于等于x， //就直接删除，下一个x因为我找的还是小于x的第一个数，当前x一定满足条件了，前面的没意义，以此类推 if (!tt) cout << “-1 “; else cout << a[tt] << “ “; a[++tt] = x; // 找到比x小的那个数以后，为什么不把x覆盖在tt上，也就是为什么不是a[tt++]，因为a[tt]比小 //，万一下一个输入的x等于刚才输入的x满足的条件的还是刚才那个a[tt];

  1. }
  2. return 0;

}

时间复杂度：O(n)<br />因为内部的while循环本质上是对栈的一个删除操作


<a name="DwSJe"></a>
## 四：单调队列（滑动窗口）
O2优化简化程序执行过程，编译期间完成一部分的计算，忽略一些没必要的代码<br />自己用数组模拟队列，比stL里面的速度要致命好处，有些笔试题中没有开O2或者O3优化，STL使用的话会慢很多。


难<br />这道题理解起来很困难<br />本质上，用一个单调递增的队列模拟一个滑动窗口<br />注意事项：<br />1：范围不是1e5+10，如果初始的值设置错误，后面也会报数组越界<br />2：y总的队列搞得很不适应，他的队列初始头为0，初始尾是-1，而且你会发现应用的时候，尾部也能用来删除，一般的队列都是头部才进行删除操作。而且他的栈跟队列也是不是很搭配，栈是0作为初始，a[++top]= x，也就是从数组下表1才开始真正存值。<br />3：理解i-k + 1 > q[hh] <br />![image.png](https://cdn.nlark.com/yuque/0/2021/png/312760/1626764319417-8cc9dcd0-f09e-402f-b899-0db109a7443a.png#height=601&id=OgE6T&margin=%5Bobject%20Object%5D&name=image.png&originHeight=601&originWidth=632&originalType=binary&ratio=1&size=107611&status=done&style=none&width=632)<br />4：因为本质上维护的滑动窗口要保证从小到大一次递增，所以当维护的队列尾部比a[i]大或者等于，就需要删除尾部元素，因为只需要维护一个单调递增的队列，实现算法优化<br />5:q[++rr] = i; 注意位置一定放在输出的前面，因为这个i可能是维护的滑动窗口最小的。<br />6：输出滑动窗口中最大的数值只需要更改 while (hh <= rr && a[q[rr]] <= a[i]) rr --;<br />7： if (i - k + 1 > q[hh]) hh++;这里一定要理解准确，i-k+1代表的是滑动窗口的最左的边界是多少，单调队列里面的内容本质上就是滑动窗口中的一个有序的简短序列，当发现维护的队列head里面存的下标小的时候，head++以后，q[head]实际存储的坐标可能已经移动了好几个，总之目的就是要求队列里面存储的下标必须是滑动窗口里面的内容。
```cpp
printf("123");
puts(""); // 这俩搭配才能换行，要是使用 cout << endl；换行会出现奇怪错误

#include <iostream>

using namespace std;

const int N = 1e6 + 10;
int a[N], q[N], n, k;

int main() {
    cin >> n >> k;
    int hh = 0, rr = -1;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (i - k + 1 > q[hh]) hh++;
        while (hh <= rr && a[q[rr]] >= a[i]) rr --;
        q[++rr] = i; 
        if (i + 1 >= k) cout << a[q[hh]] << " ";
    }
    cout << endl;
    hh = 0;
    rr = -1;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (i - k + 1 > q[hh]) hh++;
        while (hh <= rr && a[q[rr]] <= a[i]) rr --;
        q[++rr] = i;
        if (i + 1 >= k) cout << a[q[hh]] << " ";
    }
    return 0;
}

时间复杂度，暴力破解的话，就是O(nK)这个数量级是非常大的。但是