下面所有單調(diào)隊(duì)列和單調(diào)棧，我使用的 雙端隊(duì)列 STL 的 deque 模擬操作

P2698 [USACO12MAR]花盆Flowerpot

題意：

給出水滴的坐標(biāo)與下落時(shí)間，你需要構(gòu)造一個(gè)盆，使他的寬度滿足
在其范圍內(nèi)能夠接住水滴時(shí)間（第一滴和最后一滴/最大與最小值）時(shí)間差大于等于k，且使得這個(gè)盆的直徑最小

思路：

會(huì)想到尺取法（雙指針）來(lái)在符合條件內(nèi)縮小范圍，同時(shí)又涉及到區(qū)間最值問(wèn)題，那么上來(lái)想就很容易想到單調(diào)隊(duì)列或者單調(diào)棧來(lái)維護(hù)區(qū)間最值
兩點(diǎn)：滿足區(qū)間最小與最大之差大于k，且使得其長(zhǎng)度最小。
(1)區(qū)間最值：由于是要進(jìn)行雙指針操作：所以選擇雙端隊(duì)列來(lái)實(shí)現(xiàn)單調(diào)隊(duì)列維護(hù)最值，且能維護(hù)在 q.front().x ~ q.back().x的區(qū)間最值

(2)在符合條件下對(duì) front/隊(duì)首進(jìn)行移動(dòng)，以達(dá)到縮小區(qū)間操作

code:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+7;
const int inf = 0x3f3f3f3f;
struct node{
    int x,y;
};
bool cmp(node a,node b){
    return a.x<b.x;
}
node arr[maxn];
deque<node>q1;
deque<node>q2;
int main(){
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>arr[i].x>>arr[i].y;
    }
    sort(arr,arr+n,cmp);
    int ans = inf;
    for(int i=0;i<n;i++){
        node tmp;
        //維護(hù)最大最小單調(diào)隊(duì)列
        while(!q1.empty()&&q1.back().y<arr[i].y) q1.pop_back();
        tmp = arr[i];
        q1.push_back(tmp);
        while(!q2.empty()&&q2.back().y>arr[i].y) q2.pop_back();
        q2.push_back(tmp);
        while(!q1.empty()&&!q2.empty()&&q1.front().y-q2.front().y>=k){
            node pos;
            if(q1.front().x<q2.front().x) {pos = q1.front(); q1.pop_front();}
            else {pos = q2.front(); q2.pop_front();}
            ans = min(ans,arr[i].x-pos.x);
        }
    }
    if(ans!=inf) cout<<ans<<endl;
    else cout<<-1<<endl;
}

View Code

P2564 [SCOI2009]生日禮物

題意：給出n個(gè)珠子，m種顏色( 用1~m的序號(hào)表示 )，然后給出每種顏色的珠子的個(gè)數(shù)以及位置，選擇出最小的區(qū)間 涵蓋所有顏色種類的珠子。

思路：(這道題感覺(jué)和單調(diào)隊(duì)列/棧沒(méi)啥關(guān)系)尺取法，如果被新放入的位置使得涵蓋了所有的顏色，就對(duì)尾部進(jìn)行收縮，減小其長(zhǎng)度。

code:

//把所有的顏色全部包含的最小長(zhǎng)度
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
const int inf = 0x3f3f3f3f;
int cont[maxn];
struct node{
    int pos,color;
}nodes[maxn];
bool cmp(node a,node b){
    return a.pos<b.pos;
}
deque<node>q1;//滑動(dòng)窗口
int main(){
    int n,m;
    cin>>n>>m;
    int cnt = 0;
    memset(cont,0,sizeof(cont));
    for(int i=1;i<=m;i++){
        int t;
        cin>>t;
        while(t--){
            int tmp;
            cin>>tmp;
            nodes[cnt++] = (node){tmp,i};
        }
    }
    sort(nodes,nodes+cnt,cmp);
    int tot = 0;
    int ans = inf;
    for(int i =0;i<cnt;i++){
        //操作：如果所有顏色全部被包含就嘗試縮短長(zhǎng)度
        //如何有效判斷顏色被全部包含？設(shè)置tot，用于統(tǒng)計(jì)當(dāng)前顏色總數(shù)
        //如果顏色在序列中大于1則pop出去
        q1.push_back(nodes[i]);
        cont[nodes[i].color]++;
        //如果是新增加的顏色提供的貢獻(xiàn)
        if(cont[nodes[i].color]==1) tot++;
        while(!q1.empty()&&cont[q1.front().color]>1){
            cont[q1.front().color]--;
            if(cont[q1.front().color]<1) tot--;
            q1.pop_front();
        }
        if(tot==m) ans = min(ans,(q1.back().pos-q1.front().pos));
    }
    cout<<ans<<endl;
    return 0;
}

View Code

P2216 [HAOI2007]理想的正方形

題意：給出a,b,n . 有一個(gè)a*b的整數(shù)組成的矩陣，現(xiàn)請(qǐng)你從中找出一個(gè)n*n的正方形區(qū)域，使得該區(qū)域所有數(shù)中的最大值和最小值的差最小。

思路：數(shù)據(jù)比較小 0<=a,b<=1000, 且每個(gè)值 小于 1e9 ( int 范圍內(nèi) )，所以暴力一點(diǎn)的思路就是使用單調(diào)隊(duì)列 ：先橫著掃一邊，使用類似滑動(dòng)窗口來(lái)限制區(qū)間大小，得到每行中的最值。然后在豎著掃一邊，求出所有正方形的 最值。最后 對(duì)每一個(gè)正方形遍歷一邊得到最值。

code:

//題意：給出一個(gè)a*b的矩陣，找出n*n的正方形區(qū)域，使得區(qū)域中素有數(shù)的最大值和最小值最小
//思路：維護(hù)所有n*n矩陣的差值，區(qū)間就利用滑動(dòng)窗口來(lái)維護(hù)最值
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+7;
const int inf = 0x3f3f3f3f;
int mt[maxn][maxn];
int maxrow[maxn][maxn];
int minrow[maxn][maxn];
int maxcol[maxn][maxn];
int mincol[maxn][maxn];
struct node{
    int val,pos;
};
deque<node>q1;
deque<node>q2;
int main(){
    int n,m,N;
    cin>>n>>m>>N;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>mt[i][j];
        }
    }
    //得到每個(gè)符合條件區(qū)間的最大值
    //先得到 每行滑動(dòng)窗口內(nèi)的最值，
    for(int i=0;i<n;i++){
        while(!q1.empty()) q1.pop_back();
        while(!q2.empty()) q2.pop_back();
        for(int j=0;j<m;j++){
            //保證單增
            while(!q1.empty()&&q1.back().val<mt[i][j])
            q1.pop_back();
            q1.push_back((node){mt[i][j],j});
            //維護(hù)滑動(dòng)窗口長(zhǎng)度
            while(!q1.empty()&&(q1.back().pos-q1.front().pos>N-1)) q1.pop_front();
            if(j>=N-1) maxrow[i][j] = q1.front().val;
            //保證單減
            while(!q2.empty()&&q2.back().val>mt[i][j])
            q2.pop_back();
            q2.push_back((node){mt[i][j],j});
            while(!q2.empty()&&(q2.back().pos-q2.front().pos>N-1)) q2.pop_front();
            if(j>=N-1) minrow[i][j] = q2.front().val;
        }
    }
    int ans = inf;
    for(int i=N-1;i<m;i++){
        while(!q1.empty()) q1.pop_back();
        while(!q2.empty()) q2.pop_back();
        for(int j=0;j<n;j++){
            while(!q1.empty()&&q1.back().val<maxrow[j][i])
            q1.pop_back();
            q1.push_back((node){maxrow[j][i],j});
            while(!q1.empty()&&(q1.back().pos-q1.front().pos>N-1)) q1.pop_front();
            if(j>=N-1) maxcol[j][i] = q1.front().val;

            while(!q2.empty()&&q2.back().val>minrow[j][i])
            q2.pop_back();
            q2.push_back((node){minrow[j][i],j});
            while(!q2.empty()&&(q2.back().pos-q2.front().pos>N-1)) q2.pop_front();
            if(j>=N-1) mincol[j][i] = q2.front().val;
        }
    }
    for(int i=N-1;i<n;i++){
        for(int j=N-1;j<m;j++){
            ans = min(ans,maxcol[i][j]-mincol[i][j]);
        }
    }
    cout<<ans<<endl;
    return 0;
}

View Code

總結(jié)

以上是生活随笔為你收集整理的luogu-单调队列/单调栈专题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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