【算法与数据结构】单调队列

目录

单调队列

使用单调队列维护滑动窗口

具体过程：

代码实现： 

复杂度分析：

使用单调队列优化动态规划

例题 

---

单调队列

单调队列(deque)是一种特殊的队列，队列中的元素始终按严格递增或者递减排列。这样就可以保证队头元素始终是最大值或者最小值。

【问题引入】

有一个数组，长度为n，给你一个区间[left,right]，求出该区间内的最小值或者最大值。

我们如果进行普通的遍历，最坏的情况下时间复杂度是O(N），遍历整个数组。

而我们如果用单调队列来维护这段区间，始终保持队列的单调性，就可以在O(1)的时间内找到该区间的最大值或者最小值，就是队头元素。

【结论】

所以单调队列的核心用途是高效维护动态窗口的极值（最大值或最小值）。

那么对于一些动态规划，如转移方程需要进行一段区间的最值计算，可以使用单调队列优化。

---

使用单调队列维护滑动窗口

题目链接：239. 滑动窗口最大值 - 力扣（LeetCode）

当窗口形成后，我们需要找到这段窗口中的最大值，暴力的方法就是对这段区间进行遍历，每个元素进行比较，选出最大值。这样做时间复杂度为O(N^2)，效率太低。

使用单调队列优化：单调队列维护该窗口，队头元素为最大元素。时间复杂度为O(N)。

具体过程：

• 创建一个单调对列，维护该队列的递减性，以保证对头元素为窗口中的最小值。
• 对于该单调队列，存放元素的下标，按值递减排列。新来一个元素（也就是滑动窗口右移一步），需要判断对头元素是否还在窗口内，所以记录下标，便于判断对头元素是否还在窗口中，如果不在，删除对头元素。
• 新来一个元素（也就是滑动窗口右移一步），每次都需要比较队尾元素与当前元素的大小，我们维护的是递减队列，如果队尾元素大于当前元素，则将当前元素的下标直接加入队列；如果队尾元素小于当前元素，则将队尾元素删除，直到队尾元素大于当前元素，再将当前元素下标加入队列，保持队列的递减性。
• 窗口形成后，统计结果即可。队头元素就是最大元素。

代码实现： 

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {//双端队列 存储数组索引deque<int> dq;vector<int> res;for(int i=0;i<nums.size();i++){//移除超出范围的队首元素while(!dq.empty()&&dq.front()<=i-k)dq.pop_front();//维护队列递减性(从队头到队尾)，移除所有小于当前元素的队尾元素 while(!dq.empty()&&nums[dq.back()]<nums[i])dq.pop_back();//当前元素入队列dq.push_back(i);//窗口形成后，统计结果，队头元素就是最大元素if(i>=k-1)res.push_back(nums[dq.front()]);}return res;}
};

 上面的写法是使用库中的deque，还可以使用数组来模拟：

#include<iostream>
using namespace std;
const int N = 1e6 + 5;int a[N], q[N];
int n, k;int main()
{cin >> n >> k;for (int i = 1; i <= n; i++) cin >> a[i];int hh = 0, tt = -1;for (int i = 1; i <= n; i++){while (hh <= tt && i - k >= q[hh]) hh++;//处理队首while (hh <= tt && a[q[tt]] <= a[i]) tt--;//处理队尾q[++tt] = i;//队尾元素加入if (i >= k) cout << a[q[hh]] << " ";//输出队首元素}cout << endl;return 0;
}

复杂度分析：

每个元素最多入队和出队一次，时间复杂度为O(N)，队列最多存储k个元素，时间复杂度为O(K)。 

---

使用单调队列优化动态规划

在动态规划中，当状态转移需要在一个窗口查找极值时，可以使用单调队列优化时间复杂度。

题目链接：P5858 「SWTR-3」Golden Sword - 洛谷

状态表示：dp[i][j]表示加入第i个材料时， 锅内的材料个数为j（包括此时加入的），此时的耐久度的最大值。

状态转移方程的分析：加入第i个材料后的最大耐久度，等于加入第i-1个材料时最大的耐久度，再加上自身的耐久度，也就是再加上a[i]*j。

状态转移方程：dp[i][j]=max(dp[i][j],dp[i-1][k]+j*a[i])，j-1<=k<=min(w,j-1+s)。

正常使用动态规划：

第一层循环遍历i。

第二层循环遍历j，填写dp[i][j]。

但是由于有求[j-1,min(w,j-1+s)]最大值的操作，所以还需一层循环求最大值。

共三层循环，时间复杂度太大，需要进行优化。

#include <iostream>
using namespace std;
long long n, m, s;
long long a[5505];
long long dp[5505][5505];int main()
{cin >> n >> w >> s;for (long long i = 1; i <= n; i++)cin >> a[i];for (long long i = 0; i <= n; i++)for (long long j = 0; j <= w; j++)dp[i][j] = -1e18;dp[0][0] = 0;//dp[i][j]选第i个材料时，此时正好j个材料的最大耐久度for (long long i = 1; i <= n; i++)for (long long j = 1; j <= w; j++)for (long long k = j - 1; k <= min(w, s + j - 1); k++)dp[i][j] = max(dp[i][j], dp[i-1][k] + a[i] * j);long long ans = -1e18;for (int i = 0; i <= w; i++)ans = max(ans, dp[n][i]);cout << ans << endl;return 0;
}

使用单调队列优化后

在第三层的遍历，求区间[j-1,min(w,j-1+s)]的最大值，可以使用单调队列优化，降低时间复杂度。

//单调队列优化
#include <iostream>
#include <deque>
using namespace std;
long long n, w, s;
long long a[5505];
long long dp[5505][5505];int main()
{cin >> n >> w >> s;for (long long i = 1; i <= n; i++)cin >> a[i];for (long long i = 0; i <= n; i++)for (long long j = 0; j <= w; j++)dp[i][j] = -1e18;dp[0][0] = 0;//dp[i][j]选第i个材料时，此时正好j个材料的最大耐久度for (long long i = 1; i <= n; i++){deque<long long> q;  //单调队列，记录区间最大值  存储索引q.push_back(w);      //下面循环中w不会进队列，需提前进队列//[j-1,min(j-1+s,w)]//从右向左遍历，因为左端点固定，而右端点使用了minfor (long long j = w; j >= 1; j--){//[j-1,min(j-1+s,w)]while (!q.empty() && q.front() > min(w, s + j - 1))q.pop_front();while (!q.empty() && dp[i - 1][q.back()] < dp[i - 1][j-1])q.pop_back();q.push_back(j-1); //比较的是q.back()和j-1位置//统计结果dp[i][j] = a[i] * j + dp[i - 1][q.front()];}}long long ans = -1e18;for (int i = 0; i <= w; i++)ans = max(ans, dp[n][i]);cout << ans << endl;return 0;
}

例题 

题目链接：1438. 绝对差不超过限制的最长连续子数组 - 力扣（LeetCode） 

 使用两个单调队列来维护窗口的最大值和最小值，结合递增队列和递减队列。当最大值减最小值超出给定的limit时，窗口的左边界右移动，直到找到符合的位置，统计结果。

class Solution {
public:int longestSubarray(vector<int>& nums, int limit) {//单调队列，维护当前窗口的最大值和最小值deque<int> queMax,queMin;int n=nums.size();int left=0,right=0,ret=0;while(right<n){//维护队列的单调性//递减while(!queMax.empty()&&queMax.back()<nums[right])queMax.pop_back();//递增while(!queMin.empty()&&queMin.back()>nums[right])queMin.pop_back();//入队列元素queMin.push_back(nums[right]);queMax.push_back(nums[right]);while(!queMin.empty()&&!queMax.empty()&&queMax.front()-queMin.front()>limit){if(nums[left]==queMin.front())queMin.pop_front();if(nums[left]==queMax.front())queMax.pop_front();left++;}ret=max(ret,right-left+1);right++;}return ret;}
};