單調隊列

就是保持隊列中的元素始終保持單調性，這個數據結構就是單調隊列

它的作用就是維護最值、求第一個比i小(大）的數的下標等等

還有個單調棧來著，不過我們可以用一個雙端隊列就足夠了

如果要維護最大值，就用單調遞減隊列，反之，用遞增隊列

1、hdu3530?Subsequence 單調隊列入門題

這題求的是最大值減去最小值不小于m不大于k的最長長度

這題用單調隊列維護最大值和最小值即可

#include<iostream> using namespace std; #define MAX 1000005 int a[MAX],deq1[MAX],deq2[MAX]; int Min[MAX],Max[MAX]; int n,m,k; int main() {while(cin>>n>>m>>k){for(int i=1;i<=n;i++)cin>>a[i];int head1=0,tail1=0;int head2=0,tail2=0;int ans=0;int now=1;for(int i=1;i<=n;i++){while(head1<tail1&&a[deq1[tail1-1]]<a[i]) tail1--;while(head2<tail2&&a[deq2[tail2-1]]>a[i]) tail2--;deq1[tail1++]=i;deq2[tail2++]=i;//cout<<head1<<head2<<endl;while(head1<tail1&&head2<tail2&&a[deq1[head1]]-a[deq2[head2]]>k){if(deq1[head1]<deq2[head2])now=deq1[head1++]+1;else now=deq2[head2++]+1;}if(head1<tail1&&head2<tail2&&a[deq1[head1]]-a[deq2[head2]]>=m){if(ans<i-now+1)ans=i-now+1;}}cout<<ans<<endl;} } hdu3530

2、poj2559 Largest Rectangle in a Histogram

求包含的最大面積，維護兩個單調隊列，隊列求第一個比i大(小）的數

#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; #define MAX 1000005 int deq[MAX]; long long L[MAX],R[MAX]; long long h[MAX]; int n; int main() {while(~scanf("%d",&n)){if(n==0) break;memset(h,-1,sizeof(h));for(int i=1;i<=n;i++)scanf("%lld",&h[i]);memset(deq,0,sizeof(deq));int head=0,tail=0;deq[tail++]=0;for(int i=1;i<=n;i++){while(head<tail&&h[deq[tail-1]]>=h[i])tail--;L[i]=deq[tail-1]+1;deq[tail++]=i;}memset(deq,0,sizeof(deq));deq[tail++]=n+1;for(int i=n;i>0;i--){while(head<tail&&h[deq[tail-1]]>=h[i])tail--;R[i]=deq[tail-1]-1;deq[tail++]=i;}long long res=0;for(int i=1;i<=n;i++){res=max(res,h[i]*(R[i]-L[i]+1));}printf("%lld\n",res);} } poj2559

3、poj2823?Sliding Window

維護兩個單調隊列求最大和最小值即可

#include<iostream> #include<stdio.h> using namespace std; #define MAX 1000000 int n,k; int deq1[MAX],deq2[MAX]; int Max[MAX],Min[MAX]; int a[MAX]; int main() {while(~scanf("%d %d",&n,&k)){int head1=0,tail1=0;int head2=0,tail2=0;for(int i=1;i<=n;i++){scanf("%d",&a[i]);while(head1<tail1&&a[deq1[tail1-1]]<a[i]) tail1--;while(head2<tail2&&a[deq2[tail2-1]]>a[i]) tail2--;deq1[tail1++]=i;deq2[tail2++]=i;while(head1<tail1&&i-deq1[head1]>=k) head1++;while(head2<tail2&&i-deq2[head2]>=k) head2++;Max[i]=a[deq1[head1]];Min[i]=a[deq2[head2]];}for(int i=k;i<=n;i++){printf("%d ",Min[i]);}putchar('\n');for(int i=k;i<=n;i++){printf("%d ",Max[i]);}putchar('\n');} } poj2559

4、poj3017?Cut the Sequence

題意是求把數列分成幾塊后每塊的最大值的最小值，注意每塊的和不超過M

題解：dp[i]表示分塊后的最小值

則dp[i]=min{dp[i],dp[j]+max(a{j+1,i} }?

這個dp可以用單調隊列優化，維護一個單調遞減隊列，然后遍歷隊列里的值

#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> #include<math.h> using namespace std; typedef long long ll; #define MAX 100005 int n; ll m; ll a[MAX]; ll dp[MAX]; struct node {int index;ll val; }deq[MAX]; int main() {while(~scanf("%d %lld",&n,&m)){bool flag=false;for(int i=1;i<=n;i++){scanf("%lld",&a[i]);if(a[i]>m)flag=true;}if(flag){printf("-1\n");continue;}else{int head=0,tail=0;int pos=1;ll sum=a[1];deq[tail].val=dp[1]=a[1];deq[tail++].index=1;for(int i=2;i<=n;i++){sum+=a[i];while(sum>m&&pos<i)sum-=a[pos],pos++;while(head<tail&&deq[tail-1].val<=a[i]) tail--;deq[tail].val=a[i];deq[tail++].index=i;while(head<tail&&deq[head].index<pos)head++;dp[i]=dp[pos-1]+deq[head].val;for(int j=head;j<tail-1;j++)dp[i]=min(dp[i],dp[deq[j].index]+deq[j+1].val);}printf("%lld\n",dp[n]);} } } poj3017

?

轉載于:https://www.cnblogs.com/zhgyki/p/9563338.html

總結

以上是生活随笔為你收集整理的单调队列总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。