基础数据结构(一):链表、单调栈、单调队列

文章目录

一、链表和邻接表

1 链表

  这里我们不采用常用的结构体加指针的方式来实现链表,因为这样每个结点都要new一下,常见笔试题中链表结点个数都是1e5~1e6级别的,光new这些结点就足以超时了。

  所以我们采用数组来模拟链表的方式。

  单链表的主要用途是可以实现邻接表这种结构,邻接表常用来存储图和树。

I 数组模拟单链表

  e[N]来存储每个结点的值,ne[N]来存储每个结点的next指针值,如下例:

基础数据结构(一):链表、单调栈、单调队列

例题:

基础数据结构(一):链表、单调栈、单调队列
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
/*e[i]储存下标为i的结点的值 ne[i]储存下标为i的结点的next指针*/
int e[N], ne[N];
/*head存储的是哨兵头结点指向的下标
idx表示下一个可用的结点的下标
*/
int head;
int idx;
//初始化
void Init()
{
    head = -1;
    idx = 0;
}
//在head后面插入值为x的结点
void add_to_head(int x)
{
    e[idx] = x;
    ne[idx] = head;
    head = idx;
    idx++;
}
//在下标为k的结点后面插入值为x的节点
void add(int k, int x)
{
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx++;
}
// 将下标是k的点后面那个点删掉
void remove(int k)
{
    /*直接把k的next指针指向ne[k]的next就行*/
    /*直接当这个点不存在就行 算法题中不要管内存泄漏*/
    ne[k] = ne[ne[k]];
}

int main()
{
    Init();
    int m;
    cin >> m;
    char op;
    int k, x;
    while (m--)
    {
        cin >> op;
        if (op == 'H')
        {
            cin >> x;
            add_to_head(x);
        }
        else if (op == 'D')
        {
            cin >> k;
            // 如果是头结点 直接让head的next指向head指向的结点的ne 即head = ne[head];
            if (k == 0) head = ne[head];
            else
            {
                /*第k个插入的数下标为k - 1*/
                remove(k - 1);
            }
        }
        else
        {
            cin >> k >> x;
            add(k - 1, x);
        }
        //cout << op << ' ';
    }
    for (int i = head; i != -1; i = ne[i])
    {
        cout << e[i] << ' ';
    }
    return 0;
}

II 数组模拟双链表

  l[i]储存下标为i结点的前继,r[i]储存下标为i结点的后继,e[i]储存下标为i结点的值。

例题:

基础数据结构(一):链表、单调栈、单调队列
#include <iostream>
using namespace std;
const int N = 1e5 + 10;

int r[N];// 后继
int l[N];// 前继
int e[N];// 值

int idx;//下一个空闲的结点

void Init()
{
    // 0作为头结点起始
    // 1作为右边界终止
    r[0] = 1;
    l[1] = 0;
    idx = 2;
}
// 在下标为k的结点右边插入值为x的结点
void add(int k, int x)
{
    e[idx] = x;
    r[idx] = r[k];
    l[idx] = k;
    l[r[k]] = idx;
    r[k] = idx;
    idx++;
}
// 在k的左边插入就等价于add(l[k], x)

// 删除下标为k的点
void remove(int k)
{
    l[r[k]] = l[k];
    r[l[k]] = r[k];
}

int main()
{
    Init();
    int m;
    cin >> m;
    char op1, op2;
    int k, x;
    while (m--)
    {
        cin >> op1;
        if (op1 == 'L')
        {
            cin >> x;
            add(0, x);
        }
        else if (op1 == 'R')
        {
            cin >> x;
            add(l[1], x);
        }
        else if (op1 == 'D')
        {
            cin >> k;
            // 第一个插入的结点下标是2
            remove(k + 1);
        }
        else if (op1 == 'I')
        {
            cin >> op2;
            if (op2 == 'L')
            {
                cin >> k >> x;
                add(l[k + 1], x);
            }
            else
            {
                cin >> k >> x;
                add(k + 1, x);
            }
        }
    }
    for (int i = r[0]; i != 1; i = r[i])
    {
        cout << e[i] << ' ';
    }
    return 0;
}

  邻接表就是开了很多个单链表放到一起,相当于每个与这个点相连的点都存在这个链表中,常用于树和图的存储。

二、栈和队列

  模拟栈:

基础数据结构(一):链表、单调栈、单调队列
#include <iostream>
#include <string>
using namespace std;

const int N = 1e5 + 10;
int Stack[N];
int top;

void Init()
{
    top = 0;
}

void Push(int x)
{
    Stack[top++] = x;
}

int Top()
{
    return Stack[top - 1];
}

bool empty()
{
    return top == 0;
}

void Pop()
{
    --top;
}

int main()
{
    int m;
    cin >> m;
    int x;
    string op;
    while (m--)
    {
        cin >> op;
        if (op == "push")
        {
            cin >> x;
            Push(x);
        }
        else if (op == "pop")
        {
            Pop();
        }
        else if (op == "empty")
        {
            if (empty()) cout << "YES" << endl;
            else cout << "NO" << endl;
        }
        else
        {
            cout << Top() << endl;
        }
    }
    return 0;
}

模拟队列:

基础数据结构(一):链表、单调栈、单调队列
#include <iostream>
#include <string>
using namespace std;

const int N = 1e5 + 10;
/*front表示队头 rear表示队尾 在队尾插入 出队列则front++*/
int Queue[N];
int front;
int rear;

void Init()
{
    front = 0;
    rear = 0;
}

void Push(int x)
{
    Queue[rear++] = x;
}

void Pop()
{
    front++;
}

bool empty()
{
    return rear <= front;
}

int Front()
{
    return Queue[front];
}


int main()
{
    int m;
    cin >> m;
    string op;
    int x;
    while (m--)
    {
        cin >> op;
        if (op == "push")
        {
            cin >> x;
            Push(x);
        }
        else if (op == "pop")
        {
            Pop();
        }
        else if (op == "empty")
        {
            cout << (empty() ? "YES" : "NO") << endl;
        }
        else
        {
            cout << Front() << endl;
        }
    }
    return 0;
}

1 单调栈和单调队列

I 单调栈

  模型题:给定一个序列,求一下在每个数左(右)边离它最近的比它小(大)的数。

  考虑方式与双指针算法类似,先考虑暴力算法,然后再去挖掘一些性质去优化时间复杂度。

  传统暴力做法就是对每个下标往前遍历,其中隐含的可以优化的点如图:

基础数据结构(一):链表、单调栈、单调队列

  因此在栈中,若ax >= ay && x < y,则ax就可以被删掉,所以栈中的序列一定是个单调的序列。

基础数据结构(一):链表、单调栈、单调队列

基础数据结构(一):链表、单调栈、单调队列

代码:

#include <iostream>
#include <stack>
using namespace std;


int main()
{
  /*栈内维护一个单调递增元素的序列
  因为若a[x] >= a[y] 且x < y 
  那么要么就输出a[y] 要么输出a[y]之前的元素 若a[y]不满足性质 即
  a[y] >= a[i],那么a[x]也一定>= a[i],所以只能输出a[x]前面的元素
  a[x]怎么也不可能输出*/
  stack<int> st;
  int n;
  cin >> n;
  int x;
  for (int i = 0; i < n; ++i)
  {
    cin >> x;
    while (!st.empty() && st.top() >= x)
    {
      st.pop();
    }
    if (st.empty()) cout << -1 << ' ';
    else cout << st.top() << ' ';
    st.push(x);
  }
  return 0;
}

  把scanfprintf来替换cin cout后,速度确实有提升:

基础数据结构(一):链表、单调栈、单调队列

  时间复杂度:对于每个元素,最多进栈一次出栈一次,所以时间复杂度是O(n).

  单调栈的几个LeetCode例题:

基础数据结构(一):链表、单调栈、单调队列
// 解法1
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) 
    {
        stack<int> st;
        int n = nums.size();
        vector<int> ret(n, -1);
        /*因为是循环数组 所以拉长取模*/
        for (int i = 2 * n - 2; i >= 0; --i)
        {
            /*倒着走 维护一个元素单调递增的栈*/
            while (!st.empty() && st.top() <= nums[i % n]) st.pop();
            if (!st.empty()) ret[i % n] = st.top();
            st.push(nums[i % n]);
        }
        return ret;
    }
};

// 解法2
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) 
    {
        /*单调栈内存一组尚未解决计算出下一个最大元素位置的递增下标
        对遍历到的每一个元素 检查栈顶元素对应的元素值是否小于当前元素值
        若小于 则让ret[st.top()] = nums[i] 然后pop掉去看前一个未解决的问题
        否则 让当前元素下标i入栈
        */
        int n = nums.size();
        vector<int> ret(n, -1);
        stack<int> st;
        for (int i = 0; i < 2 * n - 1 ; ++i)
        {
            while (!st.empty() && nums[st.top()] < nums[i % n])
            {
                ret[st.top()] = nums[i % n];
                st.pop();
            }
            st.push(i % n);
        }
        return ret;
    }
};
基础数据结构(一):链表、单调栈、单调队列
class Solution {
public:
    vector<int> nextLargerNodes(ListNode* head) 
    {
        auto cur = head;
        int n = 0;
        while (cur != nullptr)
        {
            cur = cur->next;
            ++n;
        }
        vector<int> ret(n, 0);
        /*栈内维护一个单调递增的下标序列 表示计算出对应ret[i]的下标i*/
        stack<pair<int, int>> st;/*结点下标 元素值 为了支持随机读取*/
        int curidx = 0;
        for (cur = head; cur != nullptr; cur = cur->next, ++curidx)
        {
            /*与数组单调栈类似 尚未栈中尚未解决的点能否通过该点解决*/
            while (!st.empty() && st.top().second < cur->val)
            {
                ret[st.top().first] = cur->val;
                st.pop();
            }
            /*然后把该店入进栈*/
            st.push({curidx, cur->val});
        }
        return ret;
    }
};

II 单调队列

  最经典的应用就是求一下滑动窗口中的最大值和最小值。

基础数据结构(一):链表、单调栈、单调队列

  单调队列和单调栈的思考方式相似,先想一个暴力做法,然后把没有用的元素删掉,看此时的队列是否有单调性。

基础数据结构(一):链表、单调栈、单调队列

  -1也是同理。

  相等的可以用新进来的那个相等的数字代表进行输出。

  所以存输出最小值的队列是一个严格单调递增的序列。

代码:

#include <iostream>
#include <deque>
using namespace std;

const int N = 1e6 + 10;

int main()
{
    int n, k;
    cin >> n >> k;
    int q[N];
    for (int i = 0; i < n; ++i) cin >> q[i];
    deque<int> dq1;// 用于输出窗口最小值元素的单调递增序列
    deque<int> dq2;// 用于输出窗口最大值元素的单调递减序列
    for (int i = 0; i < n; ++i)
    {
        /*看看队首元素是否出了窗口*/
        if (!dq1.empty() && dq1.front() < i - k + 1) dq1.pop_front();
        /*维护队列的单调递增
        输出最小值时 如果队列队尾的元素大于等于此轮入窗口的q[i] 
        q[i]是后入窗口的 存在窗口内时间更长 
        那根本没有那个大元素输出的可能性
        */
        /*这里大于等于可以换大于*/
        while (!dq1.empty() && q[dq1.back()] >= q[i]) dq1.pop_back();
        /*队列中存下标 方便看队首元素是否出界*/
        dq1.push_back(i);
        if (i + 1 >= k)
        {
            printf("%d ", q[dq1.front()]);
        }
    }
    printf("\n");
    for (int i = 0; i < n; ++i)
    {
        /*看看队首元素是否出了窗口*/
        if (!dq2.empty() && i - k + 1 > dq2.front()) dq2.pop_front();
        /*维护队列的单调递减
        输出最大值时 如果队列队尾的元素小于等于此轮入窗口的q[i] 
        q[i]是后入窗口的 存在窗口内时间更长 
        那根本没有那个小元素输出的可能性*/
        /*这里小于等于可以换小于*/
        while (!dq2.empty() && q[dq2.back()] <= q[i]) dq2.pop_back();
        dq2.push_back(i);
        if (i + 1 >= k)
        {
            printf("%d ", q[dq2.front()]);
        }
    }
    return 0;
}

  刷了LeetCode题以后更好的写法:当这次移出窗口的元素是最大值或最小值时,才需要让单调队列的队头出队列。

#include <iostream>
#include <deque>
using namespace std;

const int N = 1e6 + 10;

int main()
{
  int n, k;
  cin >> n >> k;
  int q[N];
  for (int i = 0; i < n; ++i) cin >> q[i];
  deque<int> q1;
  deque<int> q2;
  for (int i = 0; i < n; ++i)
  {
    /*若待移除元素是队头 则让队头出队列*/
    if (!q1.empty() && i - k >= 0 && q1.front() == q[i - k]) q1.pop_front();
    /*求窗口最小值时,出现在我之前比我大的元素都不可能是最小值*/
    /*这里不是以下标来确定排除队首元素的 所以这里大于不能换大于等于*/
    while (!q1.empty() && q1.back() > q[i]) q1.pop_back();
    q1.push_back(q[i]);
    if (i + 1 >= k)
    {
      cout << q1.front() << ' ';
    }
  }
  cout << endl;
  for (int i = 0; i < n; ++i)
  {
    /*若待移除元素是队头 则让队头出队列*/
    if (!q2.empty() && i - k >= 0 && q2.front() == q[i - k]) q2.pop_front();
    /*求窗口最大值时,出现在我之前比我小的元素都不可能是最大值*/
    /*这里不是以下标来确定排除队首元素的 所以这里小于不能换小于等于*/
    while (!q2.empty() && q2.back() < q[i]) q2.pop_back();
    q2.push_back(q[i]);
    if (i + 1 >= k) cout << q2.front() << ' ';
  }
  return 0;
}

  LeetCode单调队列例题:

基础数据结构(一):链表、单调栈、单调队列
class MaxQueue {
public:
    MaxQueue() 
    {
    }
    
    int max_value() 
    {
        if (q2.empty()) return -1;
        // 返回单调队列q2队首元素
        return q2.front();
    }
    
    void push_back(int value) 
    {
        q1.push(value);
        // 比value小的元素都没机会输出 维护单调递减(非严格)的队列q2
        // 每个元素最多出队一次 摊到每个元素平均时间复杂度为O(1)
        while (!q2.empty() && q2.back() < value) q2.pop_back();
        q2.push_back(value);
    }
    
    int pop_front() 
    {
        if (q2.empty()) return -1;
        int val = q1.front();
        q1.pop();
        // 若弹出的元素就是最大元素 则需要把双向队列的队首元素也弹出以保持一直
        if (val == q2.front()) q2.pop_front();
        return val;
    }
private:
    queue<int> q1;// 用来存储队列元素以应对pop_front
    deque<int> q2;// 作为一个单调递减的队列来O(1)的返回max_value.
};
基础数据结构(一):链表、单调栈、单调队列
class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) 
    {
        int n = nums.size();
        int ret = 0;
        deque<int> q1;// 用于输出最大值单调递减序列 值,下标
        deque<int> q2;// 用于输出最小值的单调递增序列 值,下标
        /*i表示以j结尾的子数组最左边能到达的位置 它不会往左走 具有单调性
        可以使用双指针算法*/
        for (int j = 0, i = 0; j < n; ++j)
        {
            /*比nums[j]小的元素都不可能是最大值*/
            while (!q1.empty() && q1.back() < nums[j]) q1.pop_back();
            /*比nums[j]大的元素都不可能是最小值*/
            while (!q2.empty() && q2.back() > nums[j]) q2.pop_back();
            q1.push_back(nums[j]);
            q2.push_back(nums[j]);
            /*若当前区间[i,j]的最大值减最小值大于limit 则i要往前走且可能移除最大或最小元素*/
            while (!q1.empty() && !q2.empty() && q1.front() - q2.front() > limit)
            {
                /*当前移除的元素如果和队头相等 就把队头移除*/
                if (nums[i] == q1.front()) q1.pop_front();
                if (nums[i] == q2.front()) q2.pop_front();
                i++;
            }
            ret = max(ret, j - i + 1);
        }
        return ret;
    }
};

三、KMP算法

  先想一下暴力做法怎么做。

  暴力做法就是两层循环,

// 枚举长串的起点
for (int i = 1; i <= n; ++i)
{
    bool flag = true;
    for (int l = i, j = 1; j <= m, l <= n; ++j, ++l)
    {
        if (s[l] != p[j]) 
        {
            flag = false;
            break;
        }
    }
    if (flag == true)
    {
        break;
    }
}

  KMP的思想:

基础数据结构(一):链表、单调栈、单调队列

  这就是next[i]的含义:以sub[i - 1]为结尾的串和以sub[0]为开头的串相等且串的长度最长,这时以sub[0]为开头的串的结尾的下一个位置的下标。

  具体代码。

#include <iostream>
using namespace std;
const int N = 1e6 + 10;

char P[N];// 子串
char S[N];// 长串
int n, m;// 子串长度 长串长度
int ne[N];// next数组

int main()
{
    cin >> n >> P >> m >> S;
    ne[0] = -1;// 0下标匹配失败回溯到-1
    ne[1] = 0;// 1下标匹配失败只能回溯到0
    int i = 2, k = 0;// 求解next[i] k储存next[i - 1]
    // 求解ne数组
    while (i < n)
    {
        /*P[i - 1]和 P[k]在匹配*/
        while (k != -1 && P[i - 1] != P[k]) k = ne[k];
        ne[i] = k + 1;
        ++i;
        ++k;
    }
    // 匹配
    i = 0;
    int j = 0;
    while (i < m)
    {
        /*S[i]和P[j]在匹配*/
        while (j != -1 && S[i] != P[j]) j = ne[j];
        /*走到这里匹配成功或j到了-1怎么也没法和i匹配 
        总之这时i需要加1 j需要加1*/
        ++i;
        ++j;
        /*如果j走到了n 说明P串匹配完成了一次 返回这时的起点 也就是i - j*/
        if (j == n)
        {
            cout << i - j << ' ';
            /*为了去寻找下一个匹配完成的成功位置
            我们可以看做是在P[n - 1]位置匹配失败
            那时的i等于i - 1
            j要回溯到j = ne[n - 1]*/
            --i;
            j = ne[n - 1];
        }
    }
    return 0;
}

储存next[i - 1]
// 求解ne数组
while (i < n)
{
/P[i - 1]和 P[k]在匹配/
while (k != -1 && P[i - 1] != P[k]) k = ne[k];
ne[i] = k + 1;
++i;
++k;
}
// 匹配
i = 0;
int j = 0;
while (i < m)
{
/S[i]和P[j]在匹配/
while (j != -1 && S[i] != P[j]) j = ne[j];
/走到这里匹配成功或j到了-1怎么也没法和i匹配
总之这时i需要加1 j需要加1
/
++i;
++j;
/如果j走到了n 说明P串匹配完成了一次 返回这时的起点 也就是i - j/
if (j == n)
{
cout << i - j << ’ ';
/为了去寻找下一个匹配完成的成功位置
我们可以看做是在P[n - 1]位置匹配失败
那时的i等于i - 1
j要回溯到j = ne[n - 1]
/
–i;
j = ne[n - 1];
}
}
return 0;
}


上一篇:HTTP 2.0 原理详细分析


下一篇:HTTP1、HTTP2优缺点