[数据结构]–单调队列

大家好，欢迎来到IT知识分享网。

1.单调队列介绍

单调队列：队列元素之间的关系具有单调性（从队首到队尾单调递增/递减），队首和队尾都可以进行入队出队（即插入删除）操作，本质是由双端队列deque实现。

2.适用问题

通常解决动态小区间中寻找极值问题。

3.模拟单调递减队列（类比单调栈）

依次加入7，8，6，2，5，五次操作后队内元素排列情况：

1：7

2：8

3：8  6

4：8  6  2

5：8  6  5

1：队内为空，7入队

2：第二个元素 8  >  7 ，7出队 ，8入队

3：第三个元素 6  < 8 ,  6入队

4：第四个元素 2  < 6,    2入队

5：第五个元素 5  > 2,    2出队，  5 < 6,  5入队

4.例题

1.滑动窗口(滑动窗口 /【模板】单调队列 – 洛谷)

有一个长为 n的序列 a，以及一个大小为 k 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。

例如：

The array is [1,3,-1,-3,5,3,6,7], and k = 3。

输入格式

输入一共有两行，第一行有两个正整数 n,k。 第二行 n 个整数，表示序列 a

输出格式

输入输出样例

输入 

8 3 1 3 -1 -3 5 3 6 7

输出

-1 -3 -3 -3 3 3 3 3 5 5 6 7

说明/提示

 AC代码：

#include <iostream> #include <algorithm> #include <deque> using namespace std; const int N = 1e6 + 10; int a[N]; deque<int> q; //存下标 int main() { int n, k; cin >> n >> k; for(int i = 0; i < n; i++ ) cin >> a[i]; for(int i = 0; i < n; i++ ) //最小值(单调递增队列(队首即为最小值)) { while(!q.empty() && i - k + 1 > q.front() ) //队头滑出窗口 q.pop_front(); while(!q.empty() && a[i] < a[q.back()] ) //去除尾部所有比新元素大的 q.pop_back(); q.push_back(i); //新元素入队 if(i + 1 >= k) { cout << a[q.front()] << " "; //输出队首 } } cout << endl; q.clear(); //清空 for(int i = 0; i < n; i++ ) //最大值(单调递减队列(队首即为最大值)) { while(!q.empty() && i - k + 1 > q.front() ) //队首滑出窗口 q.pop_front(); while(!q.empty() && a[i] > a[q.back()] ) //新元素比队尾元素大 q.pop_back(); q.push_back(i); //新元素入队 if(i + 1 >= k) { cout << a[q.front()] << " "; } } cout << endl; return 0; }

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

给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。

如果不存在满足条件的子数组，则返回 0 。

示例 1：

示例 2：

示例 3：

提示：

题解：滑动窗口 + 单调队列

在代码中，使用两个单调队列，一个单调递增队列 qmin 维护最小值，一个单调递减队列 qmax 维护最大值。这样我们只需要计算两个队列的队首的差值，即可知道当前窗口是否满足条件。

AC代码：

class Solution { public: int longestSubarray(vector<int>& nums, int limit) { deque<int> qmin, qmax; //两个单调队列,维护最大值最小值 int l = 0, r = 0; //下标 int ans = 0; //保存最长连续子数组长度 while(r < nums.size() ) { while(!qmin.empty() && qmin.back() > nums[r] ) //单调递增队列 qmin.pop_back(); while(!qmax.empty() && qmax.back() < nums[r] ) //单调递减队列 qmax.pop_back(); qmin.push_back(nums[r]); qmax.push_back(nums[r]); while(!qmin.empty() && !qmax.empty() && qmax.front() - qmin.front() > limit ) { if(nums[l] == qmax.front() ) qmax.pop_front(); if(nums[l] == qmin.front() ) qmin.pop_front(); l ++; } ans = max(ans, r - l + 1); //更新 r ++; } return ans; } };