data_structure_1

2020-07-18

这段时间噬月在进行数据结构和算法的复习和学习！

这篇博客将包括链表、栈与队列，以及如何使用数组来模拟他们的内容。

我们也会提及单调栈和单调队列，并讨论他们的思想。

本篇算法模板来自AcWing的y总。

总览

以下是本篇内容：

链表和邻接表
栈与队列

链表

链表是线性表的一种，顾名思义，它是一条链，不同的节点之间由指针连接。在实现上可能会有首元是否为空的差异，不过那不是本篇博客讨论的重点。

可以使用结构体和指针来实现链表，这种动态链表一半在面试时比较常见，但笔试或写算法题一般不会使用这种写法——因为每次通过指针创建新节点的操作太慢了。接下来主要讨论使用数组来模拟链表，这种方法实现的链表也称为静态链表。

单链表

单链表一般用来写邻接表，而邻接表一般用来存树和图。

如何使用数组来模拟链表？我们可以考虑通过数组下标建立联系，开多个数组来表示链表节点的不同成员。

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

// 初始化
void init()
{
    head = -1;
    idx = 0;
}

// 在链表头插入一个数a
void insert(int a)
{
    e[idx] = a, ne[idx] = head, head = idx ++ ;
}

// 将头结点删除，需要保证头结点存在
void remove()
{
    head = ne[head];
}

注：静态链表体现出的思想是使用数组来模拟堆内存，从而省去动态内存申请的耗时过程，而idx正可以看作这样一个“堆内存指针”，它指示了我们用来模拟堆内存的数组究竟消耗了多少。idx从 0 到N - 1，这些idx指过的数字可以理解成“内存地址”，因为从链表的形式来看，这些数字确实在模拟中充当了这样的角色。

双链表

双链表一般用来优化某些问题。

// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
int e[N], l[N], r[N], idx;

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

// 在节点a的右边插入一个数x
void insert(int a, int x)
{
    e[idx] = x;
    l[idx] = a, r[idx] = r[a];
    l[r[a]] = idx, r[a] = idx ++ ;
}

// 删除节点a
void remove(int a)
{
    l[r[a]] = l[a];
    r[l[a]] = r[a];
}

使用数组模拟的静态链表最大的优势就是快，因为它不需要创建和销毁对象的过程（如果你使用C++的话，struct依然是具有默认构造和析构函数的），并且代码更加简洁。缺点是数据的上限和内存的利用率——但我们写算法题时关心的是如何在一秒内跑完题目，内存泄漏（尽管很糟糕）却不属于解题时我们需要关心的事情。但写工程时应该多加留心。using namespace std;写在开头的这种“恶劣行径”也是同样的道理。

栈与队列

栈与队列都是老熟人了，十分简单。栈是一个先进后出的桶，队列则是一个先进先出的管子。

栈

// tt表示栈顶
int stk[N], tt = 0;

// 向栈顶插入一个数
stk[ ++ tt] = x;

// 从栈顶弹出一个数
tt -- ;

// 栈顶的值
stk[tt];

// 判断栈是否为空
if (tt > 0)
{

}

单调栈

这里插播一个比较神奇的题：单调栈（说它神奇当然是因为我见识少了qwq

这个题有一个很容易想到的暴力解法，即二重for循环，第一重遍历数列的所有元素，第二重从该元素起，往前搜寻比小的第一个元素并且输出，找不到就输出1。这个解法颇有点双指针算法的既视感，然而这个暴力解法最差的情况是$O(n^2)$。

与双指针算法类似的，我们的思路是观察一下这个暴力解法中有没有蕴含着某种单调性。而很容易观察出来的一点是：
假如有两个相邻的数$a, b$且$a \gt b$，那么在$b$之后遍历到的数中，$a$明显永远不会被当成答案输出，因为根据题意，$b$总是更优的。

于是我们可以使用一个栈来存储遍历到的数，并在遇到以上的情况时，不断地从栈里取数，直到栈顶元素小于当前遍历到的数，这就找到了当前数的解——然后我们再将当前数压栈。用这样的方法，我们将得到一个单调栈，即栈内的元素是具有单调性的，在本题的体现就是栈内的元素总是从小到大的。

以下是代码实现，可以看到十分的简洁：

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 1e5 + 10;
int stk[N], tt = 0;

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;

    }

    return 0;
}

单调栈的适用题型也基本就是上述类似问法的题型了。可以提取出核心部分的模板如下：

// 常见模型：找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i <= n; i ++ ) {
    while (tt && check(stk[tt], i)) tt -- ;
    stk[ ++ tt] = i;
}

我想，如果有一个场景，在遍历数据的时候就已经可以对解按照优先级排序，那么单调栈就可以用来解这个题，但我一时还没想到什么其他的好例子。

队列

普通队列

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

// 向队尾插入一个数
q[ ++ tt] = x;

// 从队头弹出一个数
hh ++ ;

// 队头的值
q[hh];

// 判断队列是否为空
if (hh <= tt)
{

}

循环队列

// hh 表示队头，tt表示队尾的后一个位置
int q[N], hh = 0, tt = 0;

// 向队尾插入一个数
q[tt ++ ] = x;
if (tt == N) tt = 0;

// 从队头弹出一个数
hh ++ ;
if (hh == N) hh = 0;

// 队头的值
q[hh];

// 判断队列是否为空
if (hh != tt)
{

}

单调队列

考虑这样一个问题：有一个给定大小的数组，又有一个给定大小的窗口，窗口从数组的左边移动到右边，每次移动一个位置。我们的任务是每次输出窗口内元素的最大值和最小值。AcWing上有一样的例题。

这个问题是能用单调队列解决的经典问题。

我们先考虑如何求最小值。对于每个窗口来说，假如窗口内有元素$a, b$且$a$位于$b$的左边并$a \gt b$，因为$a$的值更大，并且会更快随着窗口的滑动而消失，那么当 $b$ 被包含在窗口内以后，$a$就永远没有机会作为答案输出。对于这样的情况，我们就可以把$a$干掉。

考虑这样的操作：窗口滑动可以使用一个队列来维护，队列中存放窗口中元素的下标，每次窗口移动时，新的下标加入到队尾，最旧的下标从队头弹出。现在我们针对求最小值做如下优化：每一次插入新的下标时，对比欲插入的下标对应的数和队尾元素对应的数的大小，当队列不为空且队尾元素对应的数比欲插入下标对应的数更大时，令队列尾指针减一，直到队列为空或队尾元素对应数小于欲插入的下标对应的数。经过这样的操作，我们将得到一个单调队列，即队列内元素所对应的值单调递增，这个队列已经排除了上述所有以后不可能作为答案输出的$a$，而我们要找出当前窗口内的最小值，只需要找到队头元素下标所对应的数即可。

求最大值则是完全对称的操作。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

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

int main() {
    int n, k;
    cin >> 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 ) {
        // 判断队尾的下标是否在滑动窗口内
        // 因为while会干掉一部分下标，因此不能每次都无脑自增
        if (hh <= tt && q[hh] < i - k + 1) hh ++ ;

        while (hh <= tt && a[q[tt]] >= a[i]) tt -- ;
        q[ ++ tt ] = i;

        if (i >= k - 1) printf("%d ", a[q[hh]]);
    }
    cout << endl;

    hh = 0, tt = -1;
    for (int i = 0; i < n; ++ i ) {
        if (hh <= tt && q[hh] < i - k + 1) hh ++ ;

        while (hh <= tt && a[q[tt]] <= a[i]) tt -- ;
        q[ ++ tt ] = i;

        if (i >= k - 1) printf("%d ", a[q[hh]]);
    }
    cout << endl;

    return 0;
}

我们可以总结一下单调队列和单调栈的共同思路：先写出朴素算法（暴搜），然后观察这个朴素算法中，是否会有无用元素进入栈或队列之中，并根据逻辑删除这些元素，观察栈或队列是否有单调性，若有，我们就可以做出优化。对于有单调性的队列或栈，找最值和找某个元素都是比较方便的，前者直接寻找端点，后者可以使用二分。

同时，这种思路和双指针算法也有一点类似。