目录
单调队列
单调队列(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)]
//从右向左遍历，因为左端点固定，而右端点使用了min
for (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;
}
};