当前位置：首页 > news >正文

数据结构——单调队列

news 来源：原创 2025/5/16 12:00:28

这篇博客我们来讨论一下单调队列的问题，其实和之前学的单调栈都是一种上通过改变操作来解决问题的一种数据结构

我们先来回忆一下单调栈的内容，这样方便将其和单调队列做区分

单调栈：(单调性从栈底到栈顶）
1.单调栈是一种栈数据结构，只能在栈顶进行插入和删除操作。
2.单调栈的特点是栈中的元素按照一定的单调性排列，常用的有单调递增和单调递减。
3.在插入新元素时，如果新元素破坏了当前的单调性，则从栈顶删除一部分元素，直到满足单调性要求。这样可以保证栈中的元素保持单调性。
4.单调栈的典型应用是在寻找下一个更大/更小元素的问题。

单调队列：
1.单调队列是一个双端队列，支持在队列两端进行插入和删除操作。
2.单调队列的特点是队列中的元素按照一定的单调性排列，常用的有单调递增和单调递减。
3.在插入新元素时，如果新元素破坏了当前的单调性，则在队尾删除一部分元素，直到满足单调性要求。这样可以保证队列中的元素保持单调性。
4.单调队列的典型应用是在滑动窗口中寻找最大/最小值的问题。

总而言之

单调队列和单调栈都是用于维护数据的单调性，但单调队列是双端队列，用于在滑动窗口中寻找最大/最小值，而单调栈是栈数据结构，用于寻找下一个更大/更小元素。

单调队列的运行过程

分析一下如何去寻找到一个窗口中的最大/最小值

[2,7,6,5,4,8,1]，假设我们的窗口大小为3，我们考虑在窗口滑动过程中，每个窗口的最大值为多少

我们的下标从1开始，当我们的下标在3之前时，我们的窗口还未形成

[2),7,6,5,4,8,1]

[2,7),6,5,4,8,1]

当下标从3开始后，我们的窗口正式形成

[(2,7,6),5,4,8,1]很明显窗口最大值为7

当我们在往后滑动的时候逐步寻找最大值

[2,(7,6,5),4,8,1]，最大值为7

[2,7,(6,5,4),8,1]，最大值为6

[2,7,6,(5,4,8),1]，最大值为8

[2,7,6,5,(4,8,1)]，最大值为8

我们用数据结构的想法来分析一下，如何才能取到那些最大值呢？（队列头部就是最大值）

假设我们有一个队列

我们在下标为1的时候将2存进去

下标为2的时候，我们在存7的时候发现2比7小，因此直接将2从队尾弹出，将7放进去

后续下标3,4,5都是直接放就行,但是当5下标的数放进去之后，7将从队头直接滑出，因为滑动窗口的大小为3，因此应当从队头滑出

后续和上面操作差不多

例题

滑动窗口的最大值

思路：滑动窗口板题，用一个双端队列去统计这个窗口的最大值即可

class Solution {  
public:  vector<int> maxInWindows(vector<int>& nums, int k) {  int n = nums.size();  vector<int> result;   deque<pair<int, int>> que;  for (int i = 0; i < n; i++) {  while (!que.empty() && que.front().second <= i - k) {  que.pop_front();  }  while (!que.empty() && que.back().first < nums[i]) {  que.pop_back();  }  que.push_back({nums[i], i});  if (i >= k - 1) {  result.push_back(que.front().first);  }  }  return result;  }  
};

P1886 滑动窗口 /【模板】单调队列

也是板题，就是再多统计一遍最小值即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k;
struct node{int x;int pos;
}a[1000005];
deque<node> que;
int f_max[1000005];
int f_min[1000005];
signed main()
{cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i].x;a[i].pos=i;} for(int i=1;i<=n;i++){while(!que.empty()&&que.back().x<a[i].x){que.pop_back();}que.push_back(a[i]);if(que.front().pos<i-k+1){que.pop_front();}if(i>=k){f_max[i]=que.front().x;}}while(!que.empty()){que.pop_back();}for(int i=1;i<=n;i++){while(!que.empty()&&que.back().x>a[i].x){que.pop_back();}que.push_back(a[i]);if(que.front().pos<i-k+1){que.pop_front();}if(i>=k){f_min[i]=que.front().x;}}for(int i=k;i<=n;i++){cout<<f_min[i]<<" ";}cout<<"\n";for(int i=k;i<=n;i++){cout<<f_max[i]<<" ";}return 0;
}

绝对差不超过限制的最长连续子数组

思路：题目说要求一个区间内（也就是一个窗口内）的最大值和最小值的差值小于limit的最长序列，我们可用两个队列去存储，一个存储最大值一个存储最小值，然后用两个指针L和R去看当前的区间大小为多少吗，如果当前最大值和最小值的区间小于限制，可以直接统计长度，否则就要去弹出前面的元素，让L指针向后滑动，然后直到有一个队列为空，或者最大值和最小值的差值小于limit为止

class Solution {
public:int longestSubarray(vector<int>& nums, int limit) {struct node{int x;int pos;}a[100005];int n=nums.size();for(int i=1;i<=n;i++){a[i].x=nums[i-1];a[i].pos=i;}deque<node> que_min;deque<node> que_max;int l=1;int ans=0;for(int r=1;r<=n;r++){while(!que_max.empty()&&que_max.back().x<=a[r].x){que_max.pop_back();}while(!que_min.empty()&&que_min.back().x>=a[r].x){que_min.pop_back();}que_max.push_back(a[r]);que_min.push_back(a[r]);while(que_max.front().x-que_min.front().x>limit&&!que_max.empty()&&!que_min.empty()){if(que_max.front().pos==l){que_max.pop_front();}if(que_min.front().pos==l){que_min.pop_front();}l++;}ans=max(ans,r-l+1);}return ans;}
};

P2698 [USACO12MAR] Flowerpot S

这题其实也一样，只不过他是给你雨滴的横坐标和纵坐标，当我们的最长下落时间和最短下落时间要差d，也就是说明纵坐标的高度要差d

首先，我们应当将雨滴按照x进行排序，让小的在前面，用两个队列去统计区间内的最大值和最小值，然后直到区间内的最大值和最小值的差值大于d时候再去统计区间内的长度，然后滑动左指针，逐渐改变范围

但是有可能左指针划到右指针的右边，所以在算值的时候要用绝对值

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,d;
int x,y;
struct node{int x;int y;int pos;
}a[100005];
bool cmp(node a,node b)
{return a.x<b.x;
}
signed main()
{cin>>n>>d;int maxn=0;int minn=0x3f3f3f3f;for(int i=1;i<=n;i++){cin>>a[i].x>>a[i].y;maxn=max(maxn,a[i].y);minn=min(minn,a[i].y);}if(maxn-minn<d){cout<<"-1\n";return 0;}sort(a+1,a+1+n,cmp);for(int i=1;i<=n;i++){a[i].pos=i;}deque<node> que_max;deque<node> que_min;int ans=0x3f3f3f3f;int l=1;for(int i=1;i<=n;i++){while(!que_max.empty()&&que_max.back().y<=a[i].y){que_max.pop_back();}while(!que_min.empty()&&que_min.back().y>=a[i].y){que_min.pop_back();}que_max.push_back(a[i]);que_min.push_back(a[i]);while(!que_max.empty()&&!que_min.empty()&&que_max.front().y-que_min.front().y>=d){ans=min(ans,abs(que_max.front().x-que_min.front().x));if(que_max.front().pos==l){que_max.pop_front();}if(que_min.front().pos==l){que_min.pop_front();}l++;}}cout<<ans;return  0;
}

单调队列的运行过程

例题

滑动窗口的最大值

P1886 滑动窗口 /【模板】单调队列

绝对差不超过限制的最长连续子数组

P2698 [USACO12MAR] Flowerpot S

相关文章：