求m区间内的最小值（洛谷P1440）
题目大意
对一序列a，从左至右扫描，取每个位置前m个数的最小值，位置为首位置时输出0,不足m个数时就取这段范围内的最小值。
解题思路
使用单调队列，保持队头存最小元素下标，从队尾更新最值，超出窗口范围时队头出队。
未知的代码
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;
int q[N],a[N],head=1,rear=0,n,m;
int main(){
scanf("%d %d",&n,&m); //使用STL容器和cin,cout会超时
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
printf("0\n");
for(int i=1;i<n;i++){
while(head<=rear&&a[q[rear]]>a[i])rear--;
q[++rear]=i;
while(head<=rear&&q[head]<=i-m)head++;
printf("%d\n",a[q[head]]);
}
return 0;
}
扫描（洛谷P2032）
题目大意
对于序列a，用一个长度为k的窗口从左至右按一单位滑动，求出每次滑动后窗口中的最大值。
解题思路
与上一题同类，换为队头存最大值即可。
未知的代码
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;
int a[N],q[N],head=1,tail=0,n,m;
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++){
while(head<=tail&&a[q[tail]]<a[i])tail--;
q[++tail]=i;
if(i>=m){
while(head<=tail&&q[head]<=i-m)head++;
printf("%d\n",a[q[head]]);
}
}
return 0;
}
切蛋糕（洛谷P1714）
题目大意
对于序列a，求连续最大个数不超过m的子序列和的最大值，序列值为整数。
解题思路
维护序列前缀和，对前缀和序列使用单调队列求最值。
未知的代码
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int a,sum[N],n,m,ans=-0x3f3f3f3f;
deque<int>q;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a;
sum[i]=sum[i-1]+a;
}
q.push_back(0); //为求前缀和需要一个初值0
for(int i=1;i<=n;i++){
while(!q.empty()&&q.front()<i-m)q.pop_front();
ans=max(ans,sum[i]-sum[q.front()]);
while(!q.empty()&&sum[q.back()]>=sum[i])q.pop_back();
q.push_back(i);
}
cout<<ans<<endl;
return 0;
}
好消息，坏消息（洛谷P2629）
题目大意
对于序列a，可以进行转动，即\(a_1\) \(a_2\) \(\cdots\) \(a_{n-1}\) \(a_n\) -> \(a_k\) \(a_{k+1}\) \(\cdots\) \(a_n\) \(a_1\) \(a_2\) \(\cdots\) \(a_{k-1}\)
求有多少种k使得序列a的前缀和始终不小于0。
解题思路
维护序列前缀和，对前缀和序列使用单调队列求最值。
未知的代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int a[N<<1],s[N<<1],ans[N<<1];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
a[n+i]=a[i];
s[i]=s[i-1]+a[i];
}
for(int i=n+1;i<=2*n-1;i++)s[i]=s[i-1]+a[i]; //将数组复制一份拼接可计算出题意需要的全部前缀和
deque<int>q;
for(int i=1;i<=2*n-1;i++){
while(!q.empty()&&s[i]<s[q.back()])q.pop_back();
q.push_back(i);
while(!q.empty()&&q.front()<i-n)q.pop_front();
if(i>=n)ans[i]=s[q.front()]-s[i-n]; //注意前缀和的计算
}
int cnt=0;
for(int i=n;i<=2*n-1;i++){
if(ans[i]>=0)cnt++;
}
cout<<cnt<<endl;
return 0;
}
良好的感觉（洛谷P2422）
题目大意
对于序列a，求出一段子序列中的最小值与子序列元素之和的乘积的最大值。
解题思路
使用单调队列（实为单调栈）维护对应最小值的极大前缀和区间，用以计算最值并更新。
未知的代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int a[N],s[N];
deque<int>q;
signed main()
{
int n;
cin>>n;
for(int i=1; i<=n; ++i){
cin>>a[i];
s[i]=s[i-1]+a[i];
}
int ans = 0;
for(int i=1; i<=n+1; ++i)
{
while(!q.empty() && a[q.back()]>a[i])
{
int idx=q.back();
q.pop_back();
int left=q.empty()?0:q.back();
ans=max(ans,(s[i-1]-s[left])*a[idx]);//保证所更新区间为极大区间
}
q.push_back(i);
}
cout<<ans<<endl;
return 0;
}
跳房子（洛谷P3957）
题目大意
解题思路
琪露诺（洛谷P1725）
题目大意
解题思路
小组队列（洛谷P2776）
题目大意
解题思路