棧（stack）和隊(duì)列（ queue ）

1.棧的定義：棧是限定僅在表頭進(jìn)行插入和刪除操作的線性表（先進(jìn)后出）

2.隊(duì)列的定義：隊(duì)列是一種特殊的線性表，特殊之處在于
它只允許在表的前端（front）進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作，
和棧一樣，隊(duì)列是一種操作受限制的線性表。

進(jìn)行插入操作的端稱(chēng)為隊(duì)尾，進(jìn)行刪除操作的端稱(chēng)為隊(duì)頭。（先進(jìn)先出）

poj 2823 單調(diào)隊(duì)列

給定一個(gè)長(zhǎng)度為n的數(shù)列，求長(zhǎng)度為k的定長(zhǎng)連續(xù)子區(qū)間
｛a1,a2,a3,a4,…,ak-1,ak｝{a2,a3,…,ak,ak+1}……中每個(gè)區(qū)間的最大值。

基于STL 雙端隊(duì)列deque的單調(diào)隊(duì)列

#include<bits/stdc++.h> using namespace std; #define N 1000005 int a[N]; //int maxq[N],minq[N]; int n,k; int main() {ios::sync_with_stdio(false);cin>>n>>k;for(int i=1;i<=n;i++)cin>>a[i];//int f=0,r=1;deque<int> dq;dq.clear();for(int i=1;i<=n;i++){while(!dq.empty()&&(a[dq.back()]>a[i]||i-dq.back()+1>k))dq.pop_back();while(!dq.empty()&&i-dq.front()+1>k)dq.pop_front();dq.push_back(i);if(i>=k) {cout<<a[dq.front()];if(i!=n) cout<<" ";}}cout<<endl;dq.clear();for(int i=1;i<=n;i++){while(!dq.empty()&&(a[dq.back()]<a[i]||i-dq.back()+1>k))dq.pop_back();while(!dq.empty()&&i-dq.front()+1>k)dq.pop_front();dq.push_back(i);if(i>=k) {cout<<a[dq.front()];if(i!=n) cout<<" ";}}cout<<endl;return 0; }

用數(shù)組模擬單調(diào)隊(duì)列

//poj 2823 單調(diào)隊(duì)列 #include<bits/stdc++.h> using namespace std; const int N=100005; int a[N]; int du[N];//單調(diào)隊(duì)列 int main() {ios::sync_with_stdio(false);int n,m;cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];//求區(qū)間最大值，建立從隊(duì)頭到隊(duì)尾單調(diào)遞減隊(duì)列 int l=0,r=1;fill(du,du+N,0);du[0]=1;if(m==1) printf("%d ",a[1]);for(int i=2;i<=n;i++){while(i-du[l]>=m&&(l<r))l++;while(r>l&&a[du[r-1]]>=a[i])r--;du[r++]=i;if(i>=m)printf("%d ",a[du[l]]);}return 0; }

hdu 5033 單調(diào)棧+計(jì)算幾何

題意：

將城市看做二維平面，建筑看做x軸上某個(gè)位置為端點(diǎn)的豎著的線段，

(xi,hi)表示在x軸xi位置有個(gè)高為hi的建筑（線段）。

有多次詢問(wèn)，每次問(wèn)人在某個(gè)平地上（x,0)能看到天空的角度

單調(diào)棧的性質(zhì)：

1.若是單調(diào)遞增棧，則元素從棧頂?shù)綏５资沁f增的
若是單調(diào)遞減棧，則元素從棧頂?shù)綏５资沁f減的

2.越靠近棧頂?shù)脑卦胶筮M(jìn)棧?

#include<bits/stdc++.h> using namespace std; #define eps 1e-8 #define LL long long #define pi acos(-1.0)const int Max=1e5+20;struct Node{double high;double x;int id;Node(){};Node(double high,double x,int id):high(high),x(x),id(id){};bool operator <(const Node &b)const{return x<b.x;}Node operator -(const Node &b)const{return Node(high-b.high,x-b.x,0);} }; Node tp[2*Max]; Node a[2*Max];double ans[2*Max];//判斷在c處的視野中，a建筑物是否能夠在c處沒(méi)有被b建筑物擋住 int cross(const struct Node &a,const struct Node &b){return a.high*b.x-b.high*a.x>0; } int judge(Node &a,Node &b,Node &c){return cross(a-c,c-b); } //求a建筑物與b處人所成角的大小 double angle(Node a,Node b){return atan((b.x-a.x)/(a.high)) ; } int n; int all;//包括詢問(wèn)的點(diǎn)數(shù)void solve(){int top=0;for(int i=0;i<all;i++){if(a[i].high==0){//是人的位置while(top>=2&&judge(tp[top-1],tp[top],a[i])) top--;//去掉凹處ans[a[i].id]+=angle(tp[top],a[i]);//cout<<angle(tp[top-1],a[i])<<endl;}else{while(top&&tp[top].high<=a[i].high) top--;//比當(dāng)前還要矮的不要while(top>=2&&judge(tp[top-1],tp[top],a[i])) top--;//去掉凹處tp[++top]=a[i];}} } int main(){int t;scanf("%d",&t);for(int cas=1;cas<=t;cas++){scanf("%d",&n);for(int i=0;i<n;i++){scanf("%lf %lf",&a[i].x,&a[i].high);}all=n;int q;scanf("%d",&q);for(int i=0;i<q;i++){scanf("%lf",&a[all].x);a[all].high=0;a[all].id=i;all++;}sort(a,a+all);memset(ans,0,sizeof(ans));solve();reverse(a,a+all); //翻轉(zhuǎn)，倒回來(lái)計(jì)算右邊的角度f(wàn)or(int i=0;i<all;i++) a[i].x=10000000-a[i].x ; //最大的x，變最小solve();printf("Case #%d:\n",cas);for(int i=0;i<q;i++){printf("%.10f\n",ans[i]*180/pi);//角度與弧度的轉(zhuǎn)化}}return 0; }

以下是大神的代碼片段：

總結(jié)

以上是生活随笔為你收集整理的算法竞赛入门与进阶 （二）单调队列、单调栈的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。