先介绍C++的STL中双端队列的使用方法。 定义双端队列deque<int>q; 双端队列对队首和队尾都可以进行操作，具体如下：
q.push_front(x);//x入队首 q.push_back(x);//x入队尾 q.pop_front();//删除队首元素 q.pop_back();//删除队尾元素
用前缀和预处理，用单调队列维护[i-m,i]区间内前缀和的最小值， (实际上求和区间是[i-m+1,i]，但是这个区间内的和用sum数组表示为sum[i]-sum[i-m]，即把sum的区间看成[i-m,i]) 则每次遍历的区间内所有元素和的最大值为sum[i]-sum[q.front()]，找出sum[i]-sum[q.front()]的最大值即可。
先来个错误示范（在洛谷上虽然能AC，但是实际上是错的）
#include <bits/stdc++.h> using namespace std; const int N=5e5+10; int n,m,x,mx,sum[N]; deque<int>q; int main() { ios::sync_with_stdio(false); cin>>n>>m; for(int i=1;i<=n;i++) { cin>>x; sum[i]=sum[i-1]+x; } for(int i=1;i<=n;i++) { while(!q.empty()&&i-q.front()>=m+1)q.pop_front(); while(!q.empty()&&sum[q.back()]>sum[i])q.pop_back(); q.push_back(i); mx=max(mx,sum[i]-sum[q.front()]); } printf("%d\n",mx); return 0; }hack数据：
输入 6 3 3 4 5 -4 -5 -6 输出 12 错误输出：9 错误原因：没考虑减去sum[0]的情况 解决办法：i从0开始循环 输入 6 3 -1 -1 -1 -1 -1 -1 输出 -1 错误输出：0 错误原因：会漏掉单个数是最大值的情况 解决办法：把取mx的位置移到第一个while之后(即先取滑动窗口区间内的sum最小值，之后再维护单调性)维护一个单调递增的双端队列，用ans数组记录队首元素，ans[i]表示a[i]及其之前的m-1个元素中(共m个元素)的最小值，所以最后输出ans[0]~ans[n-1]即可。
#include <bits/stdc++.h> using namespace std; const int N=2e6+10; int n,m,a[N],ans[N]; deque<int>q;//定义双端队列q，用来存放下标i int main() { ios::sync_with_stdio(false); cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) { while(!q.empty()&&i-q.front()>=m)//若队首元素与现在遍历的元素下标之差大于等于m，则删除队首元素 q.pop_front(); while(!q.empty()&&a[q.back()]>a[i])//若队尾元素大于现在遍历的元素，说明现在出现了比之前小的值，则删除队尾元素 q.pop_back(); q.push_back(i); ans[i]=a[q.front()]; } for(int i=0;i<=n-1;i++) printf("%d\n",ans[i]); return 0; }维护一个单调递减队列，也就是维护[i-m+1,i]区间内a[i]的最大值(即队列队首元素)。
#include <bits/stdc++.h> const int N=2e6+10; using namespace std; int n,m,a[N],ans[N]; deque<int>q; int main() { ios::sync_with_stdio(false); cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) { while(!q.empty()&&i-q.front()>=m) q.pop_front(); while(!q.empty()&&a[q.back()]<a[i]) q.pop_back(); q.push_back(i); ans[i]=a[q.front()]; } for(int i=m;i<=n;i++) printf("%d\n",ans[i]); return 0; }维护两个单调队列，一个递增，一个递减，开两个数组分别记录两个队列的队首元素，最后注意从下标m开始输出答案。
#include <bits/stdc++.h> using namespace std; const int N=1e6+10; int n,m,a[N],mi[N],mx[N]; deque<int>q1,q2;//q1为递增队列，q2为递减队列 int main() { ios::sync_with_stdio(false); cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) { while(!q1.empty()&&i-q1.front()>=m) q1.pop_front(); while(!q1.empty()&&a[q1.back()]>a[i]) q1.pop_back(); q1.push_back(i); while(!q2.empty()&&i-q2.front()>=m) q2.pop_front(); while(!q2.empty()&&a[q2.back()]<a[i]) q2.pop_back(); q2.push_back(i); mi[i]=a[q1.front()]; mx[i]=a[q2.front()]; } for(int i=m;i<=n;i++) i==n?printf("%d\n",mi[i]):printf("%d ",mi[i]); for(int i=m;i<=n;i++) i==n?printf("%d\n",mx[i]):printf("%d ",mx[i]); return 0; }断环为链，把a[1]~a[n-1]接在a[n]之后，形成一个长度为2*n-1的序列，滑动窗口长度为n。 前缀和预处理，用单调队列维护前缀和的最小值，[i-m,i]区间内sum最小值为sum[q.front()]，只要保证该区间内和的最小值sum[q.front()]-sum[i-n]>=0，则可以保证在[i-m+1,i]区间内所有元素和或者部分元素和都大于等于0。
#include <bits/stdc++.h> using namespace std; const int N=2e6+10; int n,ans,a[N],sum[N]; deque<int>q; int main() { ios::sync_with_stdio(false); cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; sum[i]=sum[i-1]+a[i]; } for(int i=n+1;i<=2*n-1;i++) { a[i]=a[i-n]; sum[i]=sum[i-1]+a[i]; } for(int i=1;i<=2*n-1;i++) { while(!q.empty()&&i-q.front()>n)//没有等于号 q.pop_front(); while(!q.empty()&&sum[q.back()]>sum[i]) q.pop_back(); q.push_back(i); if(i>=n&&sum[q.front()]-sum[i-n]>=0)ans++; } printf("%d\n",ans); return 0; }单调队列优化DP。 用dp[i]表示到达i位置时的和，滑动窗口长度为m=r-l+1，用单调队列维护dp值的滑动窗口，最后在[n-r+1,n]区间内找到dp最大值即为答案。注释详见代码。
#include <bits/stdc++.h> using namespace std; const int N=2e5+10,inf=0x3f3f3f3f; int n,m,l,r,mx,a[N],dp[N]; deque<int>q; int main() { ios::sync_with_stdio(false); cin>>n>>l>>r; m=r-l+1;//m为滑动窗口大小 for(int i=0;i<=n;i++) cin>>a[i]; memset(dp,-inf,sizeof(dp));//注意dp初始化为最小值 dp[0]=0; for(int i=0;i<=n-l;i++) { while(!q.empty()&&i-q.front()>=m)q.pop_front(); while(!q.empty()&&dp[q.back()]<dp[i])q.pop_back(); //维护一个递减队列，队首为[i-m+1,i]区间内dp的最大值 q.push_back(i); dp[i+l]=dp[q.front()]+a[i+l];//dp[i+l]表示跳到i+l位置时的最大和 } mx=-inf; for(int i=n-r+1;i<=n;i++) mx=max(mx,dp[i]); printf("%d\n",mx); return 0; }洛谷数据很水，写了个O(n2)的暴力竟然也能AC…
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+10; ll n,l,r,mx,a[N],sum[N]; int main() { ios::sync_with_stdio(false); cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; sum[i]=sum[i-1]+a[i]; } for(int i=1;i<=n;i++) { l=r=i; while(l>=1) { if(a[l-1]>a[i])l--; else break; } while(r<=n) { if(a[r+1]>a[i])r++; else break; } mx=max(mx,a[i]*(sum[r]-sum[l-1])); } printf("%lld\n",mx); return 0; }然而，1e5的数据规模，要避免TLE，只能写O(n)或者O(nlogn)的算法。
开l、r两个数组记录a[i]作为区间[ l [i] , r [i] ]内的最小值最远能扩展到的左端点l[i]和右端点r[i]，正逆遍历各一次，用两个双端队列分别求出 l [i] 和 r [i]，最后找最大值及其左右端点即可。 至于如何用单调队列的思想得到 l、r 数组，再详细说明一下。以找 r[i] 为例，遍历1~n，每次保证队尾是队列中的最小值，如果不是，则队尾出队，并记录以队尾为最小值时能扩展到的最远的右端点，遍历完之后剩下的队列中所有的位置对应的右端点都是n，比如说a[q.back()]是区间[q.back(),n]内的最小值，即r[q.back()]=n。 不知道为什么cin前面加了ios::sync_with_stdio(false)还是超时，改成scanf就好了，可能是POJ这题Special Judge的锅… 以下给出O(n)算法的单调队列优化代码：
#include <deque> #include <cstdio> using namespace std; const int N=1e5+10; typedef long long ll; ll n,mx,ansl,ansr,a[N],l[N],r[N],sum[N]; deque<ll>q1,q2; int main() { scanf("%lld",&n); for(int i=1;i<=n;i++) { scanf("%lld",&a[i]); sum[i]=sum[i-1]+a[i]; } for(int i=1;i<=n;i++) { while(!q1.empty()&&a[q1.back()]>a[i])//每次保证队尾是队列中的最小值，如果不是，则队尾出队，并记录以队尾为最小值时所能扩展到的右端点 { r[q1.back()]=i-1; q1.pop_back(); } q1.push_back(i); } while(!q1.empty())//剩下的队列中所有位置对应的右端点都是n { r[q1.back()]=n; q1.pop_back(); } for(int i=n;i>=1;i--) { while(!q2.empty()&&a[q2.back()]>a[i]) { l[q2.back()]=i+1; q2.pop_back(); } q2.push_back(i); } while(!q2.empty()) { l[q2.back()]=1; q2.pop_back(); } mx=0; for(int i=1;i<=n;i++) { if(a[i]*(sum[r[i]]-sum[l[i]-1])>=mx)//注意有等于号，从而保证a[i]全部等于0的情况也会记录ansl和ansr { mx=a[i]*(sum[r[i]]-sum[l[i]-1]); ansl=l[i]; ansr=r[i]; } } printf("%lld\n%lld %lld\n",mx,ansl,ansr); return 0; }做完我们发现只对双端队列的尾部进行了操作，所以这题也可以用栈来解决，也就是所谓的“单调栈”。
