单调队列

__Green_tick__ · 2025-07-10 18:59:28 · 算法·理论

单调队列

引入

在学习单调队列前，让我们先来看一道例题。

P1886 滑动窗口 /【模板】单调队列
题目大意

本题大意是给出一个长度为 n 的数组，编程输出每 k 个连续的数中的最大值和最小值。

暴力解法

最暴力的想法很简单，对于每一段 i \sim i+k-1 的序列，逐个比较来找出最大值（和最小值），时间复杂度约为 O(n \times k)。

很显然，这其中进行了大量重复工作，除了开头 k-1 个和结尾 k-1 个数之外，每个数都进行了 k 次比较，而题中 100\% 的数据为 n \le 1000000，当 k 稍大的情况下，显然会 TLE。

这时所用到的就是单调队列了。

定义

顾名思义，单调队列的重点分为「单调」和「队列」。

单调：很好理解，即队列内元素有序。
队列：元素只能从队头和队尾进行操作。

作用

求解关于一个区间内的极值问题。

回归问题

样例输入如下：

8 3
1 3 -1 -3 5 3 6 7

因为我们始终要维护队列保证其递增的特点，所以在 a_i \le a_{i-1} 时，就会将 所有比当前值小的元素 出队，这可能不是很好理解，我们来手玩一下这个样例：

操作	队列状态
1 入队	\{1\}
3 比 1 大，3 入队，不删除	\{1,3\}
-1 比 3 小，3 出队；-1 比 1 小，1 出队；-1 入队	\{-1\}
-3 比 -1 小，-1 出队；-3 入队	\{-3\}
5 比 -3 大，5 入队	\{-3,5\}
3 比 5 小，5 出队；3 入队	\{-3,3\}
-3 已经在窗体外，所以 -3 出队；6 比 3 大，6 入队	\{3,6\}
7 比 6 大，7 入队	\{3,6,7\}

我们已经熟悉了单调队列的写法，尝试通过本题。

参考程序

#include<bits/stdc++.h>
using namespace std;
#define var long long
#define ln "\n"
template<typename... Args>
void print(Args... args){
    return;
}

template<typename T,typename... Args>
void print(T first,Args... args){
    cerr<<first<<" ";
    print(args...);
    return;
}

template<typename... Args>
void debug(Args... args){
    cerr<<"----------------------------------"<<ln;
    cerr<<"Debug :"<<ln;
    print(args...);
    cerr<<ln<<"Time : "<<clock()<<ln;
    cerr<<"----------------------------------"<<ln;
    return;
}

const var N=1e6+10;
var x;
deque<pair<var,var>> Q;
deque<pair<var,var>> R;
var maxx[N],minn[N];
var n,m,k,sum=1;
pair<var,var> lin;
int main(){
    ios::sync_with_stdio();
    cin.tie();
    cout.tie();

    cin>>n>>k;
    for(var i=1;i<=n;i++){
        cin>>x

        lin.first=i;
        lin.second=x;

        while(!Q.empty() && x>Q.back().second) Q.pop_back();
        while(!R.empty() && x<R.back().second) R.pop_back();

        Q.push_back(lin);
        R.push_back(lin);

        while(i-k>=Q.front().first) Q.pop_front();
        while(i-k>=R.front().first) R.pop_front();

        if(i>=k){
            maxx[sum]=Q.front().second;
            minn[sum]=R.front().second;
            sum++;
        }
    }

    for(var i=1;i<sum;i++){
        cout<<minn[i]<<" ";
    }
    cout<<ln;

    for(var i=1;i<sum;i++){
        cout<<maxx[i]<<" ";
    }
    cout<<ln;
    return 0;
}

例题讲解

P2698 [USACO12MAR] Flowerpot S

题目大意

老板需要你帮忙浇花。给出 N 滴水的坐标，y 表示水滴的高度，x 表示它下落到 x 轴的位置。

每滴水以每秒 1 个单位长度的速度下落。你需要把花盆放在 x 轴上的某个位置，使得从被花盆接着的第 1 滴水开始，到被花盆接着的最后 1 滴水结束，之间的时间差至少为 D。

我们认为，只要水滴落到 x 轴上，与花盆的边沿对齐，就认为被接住。给出 N 滴水的坐标和 D 的大小，请算出最小的花盆的宽度 W。

如何求解

首先：

所在的区间端点一定在水滴上。

暴力的解法：时间复杂度 O(n^2)，肯定会炸。

因为在右端点右移时，花费时间只增不减，于是我们想到了双指针，时间复杂度 O(n)。

思路明朗，动手实践！

参考代码

#include<bits/stdc++.h>
using namespace std;
#define var long long
#define ln "\n"
template<typename... Args>
void print(Args... args){
    return;
}

template<typename T,typename... Args>
void print(T first,Args... args){
    cerr<<first<<" ";
    print(args...);
    return;
}

template<typename... Args>
void debug(Args... args){
    cerr<<"----------------------------------"<<ln;
    cerr<<"Debug :"<<ln;
    print(args...);
    cerr<<ln<<"Time : "<<clock()<<ln;
    cerr<<"----------------------------------"<<ln;
    return;
}

const var MaxN=1e5+10;
var n,k;
pair<var,var> arr[MaxN];
deque<var> que_max;
deque<var> que_min;
var ans=LONG_LONG_MAX;

int main(){
    ios::sync_with_stdio();
    cin.tie();
    cout.tie();

    cin>>n>>k;
    for(var i=1;i<=n;i++){
        cin>>arr[i].first>>arr[i].second;
    }

    sort(arr+1,arr+1+n);

    que_max.push_back(1);
    que_min.push_back(1);

    var r=1;
    for(var l=1;l<=n;l++){
        while(que_max.size() && que_max.front()<l) que_max.pop_front();
        while(que_min.size() && que_min.front()<l) que_min.pop_front();

        while(r<n && arr[que_max.front()].second-arr[que_min.front()].second<k){
            r++;

            while(que_max.size() && arr[que_max.back()].second<=arr[r].second) que_max.pop_back();
            que_max.push_back(r);
            while(que_min.size() && arr[que_min.back()].second>=arr[r].second) que_min.pop_back();
            que_min.push_back(r);
        }

        if(arr[que_max.front()].second-arr[que_min.front()].second>=k){
            ans=min(ans,arr[r].first-arr[l].first);
        }else{
            break;
        }
    }

    if(ans==LONG_LONG_MAX){
        cout<<"-1"<<ln;
    }else{
        cout<<ans<<ln;
    }
    return 0;
}