企业官网建设流程全解析

目录

一.前言

二.队列

1.队列的认识

2.对队列的优化

2.循环队列代码实现

三.单调队列

四.相关练习

五.感言

一.前言

队列是与栈一同学习的线性表下的数据结构，本文章将介绍队列的基本知识以及相关技巧——单调队列。当然，队列的应用远不止于此，像是各种搜索算法等等，以后我会在相关算法中提到。

二.队列

1.队列的认识

队列是线性表中的一个重要数据结构，核心特征是先进先出，只允许对头与尾部的元素进行操作

实现思路

定义一个结构体，里面有一个数组和head与tail两个指针，数组容量最大设为Maxsize

关键是head队头与tail队尾的定义，可以将head定义为指向队头元素位置的指针，tail定义为执行队尾元素下一个位置的指针，也可以将head定义为指向队头元素前一个位置的指针，tail定义为执行队尾元素位置的指针

出队时head向后移动并返回元素，入队时tail向后移动并传入元素，q->head==q->tail时队列为空

当q->tail==Maxsize-1（物理存储）时则满

2.对队列的优化

循环队列

按照上述的队列实现思路，我们会发现，当队列的head，tail指针不断向后移动时，两指针可能都到达Maxsize-1,这时会出现假满的情况，明明数组前面还有很多空间，结果全部被浪费了

为了能够利用，我们利用取模操作，形成逻辑上的圆环（当然也可以让head与tail重新指向头部，但这样写就麻烦了），我们专门留出一个空间，来判断满还是空，当（tail+1）%Maxsize==head时为满，当tail==head时为空

双端队列

有时，队列需要对队首和队尾都进行入队出队操作（比如单调队列解决滑动窗口问题)，这就是双端队列，双端队列可以退化为普通队列与栈

双端队列是在普通循环队列上做了head与tail指针可以前后移动的改变，注意继续取模运算

2.循环队列代码实现

#include "Queue.h" //struct Queue{ //我们建立一个循环队列，这里是循环队列 // int data[Maxsize]; // int head,tail; //}; //下面队列是创建，销毁，判空，判满，增加，删除，查询元素个数的相关代码 void ini_queue(Queue *& p){//这里我们规定head指向队首的前一个元素,tail指向队尾最后一个元素 //也可以将head定义为指向队首元素，tail定义为指向队尾元素的下一个位置 p=new Queue; p->head=p->tail=0; //这里容易踩坑，如果初始化为-1，会导致越界 } void del_queue(Queue *& p){ delete p; p=nullptr; } bool full(Queue * p){ return ((p->tail+1)%Maxsize==p->head); } bool empty(Queue * p){ return (p->tail==p->head); } bool enqueue(Queue * p,int x){ //传入元素，并添加 if(full(p)) return false; p->tail=(p->tail+1)%Maxsize; p->data[p->tail]=x; return true; } bool dequeue(Queue *p ,int &x){ //同时给出删除元素 if(empty(p)) return false; p->head=(p->head+1)%Maxsize; x=p->data[p->head]; return true; } int ele_num(Queue * p){ return (p->tail-p->head+Maxsize)%Maxsize; }

三.单调队列

单调队列主要解决滑动窗口求解最值问题与用滑动窗口进行DP优化问题，借助双端队列来实现

单调栈通过在队列中维护一个单调递增或单调递减的序列，使得队首元素始终是当前窗口的最值

其实就是人为定制了特殊的入队，出队与查询最值的操作

以下是寻找窗口中的最大元素的模板代码

vector<int> maxSlidingWindow(vector<int>& nums, int k) { deque<int> dq; // 存下标 vector<int> res; for (int i = 0; i < nums.size(); i++) { // 1. 队尾弹出：维护单调递减 while (!dq.empty() && nums[dq.back()] <= nums[i]) { dq.pop_back(); } // 2. 入队 dq.push_back(i); // 3. 队首弹出：超出窗口范围 if (dq.front() <= i - k) { dq.pop_front(); } // 4. 记录答案：窗口形成后 if (i >= k - 1) { res.push_back(nums[dq.front()]); } } return res; }

如果想要求解最小元素，只需要将 nums[dq.back()] <= nums[i]改为 nums[dq.back()] >= nums[i]即可

四.相关练习

下面是关于单调队列的习题

这道题简单应用模板就好

#include <iostream> #include <deque> #include <vector> using namespace std; const int N=1e6+10; long long arr[N]; int main(){ int n,k; deque<long long>q; cin>>n>>k; for(int i=0;i<n;i++ ){ cin>>arr[i]; } for(int i=0;i<n;i++){ if(!q.empty()&&q.front()<=i-k){ q.pop_front(); } while(!q.empty()&&arr[q.back()]>=arr[i]){ q.pop_back(); } q.push_back(i); if(i>=k-1){ cout<<arr[q.front()]<<" "; } } cout<<endl; q.clear(); for(int i=0;i<n;i++){ if(!q.empty()&&q.front()<=i-k){ q.pop_front(); } while(!q.empty()&&arr[q.back()]<=arr[i]){ q.pop_back(); } q.push_back(i); if(i>=k-1){ cout<<arr[q.front()]<<" "; } } return 0; }

这道题注意前缀和与单调队列结合，需要去对前缀和做出转化，化为在滑动窗口中寻找最小值

下面是代码

#include <iostream> #include <algorithm> #include <deque> #include <climits> using namespace std; const int N = 5e5 + 10; long long s[N]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) { int x; cin >> x; s[i] = s[i - 1] + x; } deque<int> q; q.push_back(0); long long ans = LLONG_MIN; for (int r = 1; r <= n; r++) { //去掉过期下标 while (!q.empty() && q.front() < r - m) q.pop_front(); //此时队列里只有 [r-m, r-1] 的候选 if (!q.empty()) ans = max(ans, s[r] - s[q.front()]); //入队 j = r（供后面的 r 使用） while (!q.empty() && s[q.back()] >= s[r]) q.pop_back(); q.push_back(r); } cout << ans << '\n'; return 0; }

五.感言

虽然算法无穷尽，但我们能通过掌握一些技巧与模板来解决大部分问题。每次做算法题时头疼是不可避免，时间也会被消耗不少，但收获和喜悦是很多的