有一类问题需要维护一段区间内的最大值或最小值，例如滑动窗口、区间最值等问题。一般情况下，我们可以使用线段树、ST表等数据结构来解决这类问题，但是这些数据结构的实现较为复杂，需要一定的时间和精力来学习和掌握。而单调队列则是一个简单而高效的数据结构，可以用来解决这类问题。
基本概念
单调队列是一种存储数据的队列，其中元素的顺序是单调递增或单调递减的。在算法竞赛中，我们一般使用两个单调队列，一个维护单调递增序列，另一个维护单调递减序列。
单调队列是一个双端队列。
单调队列的应用：
滑动窗口
滑动窗口是一类问题，需要在一个长度为n的序列中，找到所有长度为k的连续子序列中的最大值或最小值。使用单调队列可以在O(n)的时间复杂度内解决该问题。
具体做法如下：
- 首先，将前k个元素插入单调队列中，并记录队列的最大值或最小值。
- 然后，从第k+1个元素开始，每次将一个新的元素插入单调队列中。
- 插入时，先将队列中所有小于等于该元素的队尾元素出队，保证队列中的元素单调递减。
- 然后，将该元素插入队尾，并记录队列的最大值或最小值。
- 最后，将长度为k的子序列的最大值或最小值输出即可。
区间最值
需要在一个长度为n的序列中，找到所有长度为k的子序列中的最大值或最小值。使用单调队列可以在O(n)的时间复杂度内解决该问题。
其实现方法与上面类似，但是需要注意：
- 区间最值问题是在不限制子序列连续性的情况下，找到子序列中的最大值或最小值。
- 而滑动窗口问题则是在限制子序列必须连续的情况下，找到所有长度为k的子序列中的最大值或最小值。
154. 滑动窗口
题目要求：给你一段长度为n的序列，并且给你一个k，使得你维护一个长度为k的子序列，并且找到整个序列中全部长度为k的子序列的所有的最小值与最大值。
示例：
8 3
1 3 -1 -3 5 3 6 7结果如下：
min: -1 -3 -3 -3 3 3
max: 3 3 5 5 6 7如果我们在使用两重for循环，如下所示：
for (int i=1;i<=n;i++){
int num=0;
for (int j=i-k+1;j<=i;j++){
num=max(num,nums[j]);
}
ans=max(ans,num);
}这样每次都重复枚举新的i的位置，并且找到其对应窗口的最大值与最小值，则时间复杂度为O（nk）。我们可以使用单调队列使得时间复杂度降低为O（nlogn）：
单调队列的过程如下：以维护滑动窗口内的最大值为例
head：单调队列头 ；tail：单调队列尾
q：单调队列存储数组，nums：原数组
k=3
注意我们的单调队列存储的是元素nums[i]的下标i
首先head与tail初始化为0（下标1表示起始元素）
- i=1，元素 1 ：此时队列为空，直接插入单调队列的尾部，tail++，此时
head=0，tail=1，q： 1 - i=2，元素 3 ：此时队列非空，可以注意到队尾元素 1 小于3，因为我们的单调队列维护最大值，所以会删除队尾元素，一直到待插入元素小于队尾元素才行，或者队列为空，tail–，然后我们找到了合适的位置，则元素 3 插入到单调队列的尾部，++tail；由于我们先出再入，此时
head=0，tail=1，q：2 - i=3，元素 -1：此时队列非空，并且待插入元素小于队尾元素，直接插入到尾部，tail++，并且此时枚举到的元素下标为 i= 3 ，此时正好是第一个长度为k的窗口，因此 head++。此时
head=1，tail=2，q：2 -1。输出队头元素：nums[q[head]]=nums[q[1]]=nums[2]=3 - i=4，元素 -3：此时队列非空，并且待插入元素小于队尾元素，直接插入到尾部，tail++，此时
head=1，tail=3，q：2 3 4。输出队头元素：nums[q[head]]=nums[q[1]]=nums[2]= 3 - i=5，元素 5 ：此时队列非空，可以注意到队尾元素小于待插入元素，所以队尾元素出队，一直到待插入元素小于队尾元素才行，或者队列为空，此时我们找到了合适的位置，则元素 5 插入到单调队列的尾部；经过了很多次的tail–后，然后++tail，此时
head=1，tail=1，q：5。输出队头元素：nums[q[head]]=nums[q[1]]=nums[5]=5 - i=6，元素 3：此时队列非空，并且待插入元素小于队尾元素，直接插入到尾部，tail++，此时
head=1，tail=2，q：5 6。输出队头元素：nums[q[head]]=nums[q[1]]=nums[5]=5 - i=7，元素 6 ：此时队列非空，可以注意到队尾元素小于待插入元素，所以队尾元素出队，一直到待插入元素小于队尾元素才行，或者队列为空，此时我们找到了合适的位置，则元素 6 插入到单调队列的尾部；经过了很多次的tail–后，然后++tail，此时
head=1，tail=1，q：7。输出队头元素：nums[q[head]]=nums[q[1]]=nums[7]=6 - i=8，元素 7 ：此时队列非空，可以注意到队尾元素小于待插入元素，所以队尾元素出队，一直到待插入元素小于队尾元素才行，或者队列为空，此时我们找到了合适的位置，则元素 7 插入到单调队列的尾部；经过了很多次的tail–后，然后++tail，此时
head=1，tail=1，q：8。输出队头元素：nums[q[head]]=nums[q[1]]=nums[8]=7
可以注意到几个问题？
- 我们在单调队列中存储的是原数组的下标值，这样便于找到原始数据以及对队列进行操作
- q[head] 表示 队头元素，这个元素是一个下标，通过**nums[q[head]]**就可以找到队头的真正数据。
- tail什么时候变我们都知道，但是什么时候
head会变？
- 当队头元素小于 i-k+1的时候。 i为窗口右端点时，i-k+1表示左端点，队头元素表示的是下标，也就是说当
队列队头元素小于窗口的左端点时，说明这个窗口已经超过了，不包含队头元素了，因此需要移动head到窗口的新的左端点位置，head++。
- 什么时候输出区间最大值？
- 当遍历下标 i>k-1的时候。k-1表示窗口的最小保持长度，例如 k=3，k-1=2，因此当 i=3的时候，i>k-1，那么表示我们正处于第一个窗口的位置（i=3，窗口包括i=1，2，3位置的元素），那么我们输出队头元素所代表的元素值。往后每遍历一个i，都需要输出一次队头，因为每次都是一个长度为k的子窗口。
同理使用STL的deque也可以实现，因为deque本身就是一个双端队列。
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <deque>
using namespace std;
#define int long long
const int N=1e6+10;
int nums[N];
int n,k;
int q[N];
signed main(){
cin>>n>>k;
for (int i=1;i<=n;i++){
cin>>nums[i];
}
deque<int> deq;
//最小值
for (int i=1;i<=n;i++){
//如果队列头超过了范围，则弹出队列头
if (!deq.empty() && deq.front()<i-k+1) deq.pop_front();
//如果待插入元素比队尾元素小，则一直找到不小的或者队列为空时插入
while (!deq.empty() && nums[i]<=nums[deq.back()]) deq.pop_back();
deq.push_back(i);
if (i>k-1) printf("%lld ",nums[deq.front()]);
}
cout<<endl;
int tail=0,head=0;
//最大值
for (int i=1;i<=n;i++){
//如果队头元素超过了窗口的范围，则队头出队
if (head<=tail && q[head]<i-k+1) head++;
//队列不为空，并且要插入的元素大于等于队列尾元素，则寻找一个不大于等于的位置，这些队尾元素都出队；或者队列为空时插入
while (head<=tail && nums[i]>=nums[q[tail]]) tail--;
q[++tail]=i;
//对每一个窗口输出队头元素
if (i>k-1) printf("%lld ",nums[q[head]]);
}
return 0;
}135. 最大子序和
题目要求：给你一个序列，在长度不超过m的情况下，找到所有长度不超过m的子序列的和的最大值是多少。
示例：
6 4
1 -3 5 1 -2 3m=4，可以得到最后四个数字的和最大，并且长度为4，不超过m，满足。
一看到子序列的区间和我们就可以想到前缀和。
因此这道题目第一个任务就完成了，我们只需要求出前缀和，并且计算在长度不超过m的情况下：
- 计算sum[i]-sum[j-1]的最大值
其中 i为m长度子序列的右端点，j为左端点，因此sum[i]-sum[j-1]表示的就是这段区间的和。
那么现在问题来了，我们如果求得者每个这样的区间的最大值呢，可以使用O（N^2）枚举所有的子区间，然后分别计算他们的最大值，不过这样做显然是超时的。
观察这个式子：要想使得sum[i]-sum[j-1]最大，因此我们不妨固定住右端点i。
然后在 [i-m+1，i] 的范围内找到一个最小的前缀和使得 sum[j-1]最小，这样就可以让 sum[i]-sum[j-1]最大。
因此问题就转换为了在 [i-m+1，i]区间内维护一个区间最小值，然后每次更新右端点 i 的时候直接计算sum[i]-sum[j-1]即可，其中 j 的位置就是前缀和最小值的位置
因此我们可以使用单调队列维护滑动窗口最小值.
维护最小值：
- 入队的操作：如果队列为空，则插入到队列尾；如果队尾元素大于待插入元素，则弹出队尾元素，一直到队尾元素小于待插入元素位置。
- 出队的操作：当队头超过了长度为 m 的窗口的范围，即q[head]在i-m+1的左边，head++
需要注意的点：
- 出队的时候我们的head需要指向窗口左端点的前一个，因为我们的前缀和的计算是 sum[i]-sum[j-1]，j的位置就是左端点的位置。
#include <iostream>
#include <string>
#include <algorithm>
#include <climits>
using namespace std;
const int N=3e5+10;
int n,m,nums[N],sum[N];
signed main(){
cin>>n>>m;
for (int i=1;i<=n;i++){
scanf("%d",&nums[i]);
sum[i]=sum[i-1]+nums[i];
}
int ans=INT_MIN;
int head=0,tail=0,q[N];
for (int i=1;i<=n;i++){
//在[i-m+1,i]的范围内找前缀和的最小值，为j，使得 sum[i]-sum[j-1]最大
if (head<=tail && q[head]<i-m){
head++;
}
ans=max(ans,sum[i]-sum[q[head]]); //每一个sum[i]-当前窗口最小值= MAXval
while (head<=tail && sum[i]<=sum[q[tail]]){
tail--;
}
q[++tail]=i;//存储的是下标i
}
cout<<ans;
return 0;
}