本文主要是介绍单调队列【总结】，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一、基本概念

单调队列是指：单调递增或单调递减的队列。所以它也有如下几个性质：
1.队列中的元素在原来的列表中的位置是由前往后的(随着循环顺序入队)。
2.队列中元素的大小是单调递增或递减的。
3.从队尾入列，队首或队尾出列
时间复杂度：O(N)

二、例题

1.最大子序和（dp+单调队列优化）

题目描述
输入一个长度为n的整数序列，从中找出一段不超过m的连续子序列，使得整个序列的和最大。
例如 1,-3,5,1,-2,3
当m=4时，S=5+1-2+3=7
当m=2或m=3时，S=5+1=6
输入
第一行两个数n,m（n,m≤300000）（n,m \leq 300000）（n,m≤300000）
第二行有n个数，要求在n个数找到最大子序和
输出
一个数，数出他们的最大子序和
样例输入

6 4
1 -3 5 1 -2 3

样例输出

7

题解：
计算区间和的问题，一般转化为连个前缀和相减的形式进行求解。我们可以先求出S[i]表示序列里前 i i i项的和，则连续子序列 [ L , R ] [L,R] [L,R]中的和就等于 S [ R ] − S [ L − 1 ] S[R]-S[L-1] S[R]−S[L−1].所以我们可以非常巧妙地将原问题转化为：找出两个位子h和t，使 S [ h ] − S [ t ] S[h]-S[t] S[h]−S[t]最大并且 y − x < = m y-x<=m y−x<=m
首先枚举右端点 i i i，当 i i i固定时，问题就变为：找到一个右端点 j j j，其中j属于 [ i − m , i − 1 ] [i-m,i-1] [i−m,i−1]这个集合,并且 S [ j ] S[j] S[j]最小.
如果我们比较一下任意的两个位子j和k,如果k<j<i，并且S[k]>=S[j]，那么对于所有大于等于i的右端点，k永远不会成为最佳选择。这是因为不但S[k]不小于S[j]，而且j离i更近，长度更不容易超过M，即j的生存能力比k更强。所以当j出现后，k就是个完全无用的位子。
以上比较可以让我们得出结论：可能成为最优选择的策论集合一定是一个“下标位置递增、对应的前缀和S的值也递增”的序列。我们可以用一个队列保存这个序列。随着右端点变从前向后扫描，我们对于每个i可以执行以下步骤：
1.判断队头决策与i的距离是否超过M的范围，若超则出队
2.此时队头就是右端点i时，左端点j的最优选择
3.不断删除队尾决策，直到队尾对应的S值小于S[i]。然后把i作为一个新的决策入队
C o d e : Code: Code:

#include<bits/stdc++.h>
#define inf 0x3f3f3f
#define N 300005
using namespace std;
int n,m;
int sum[N],q[N];
int main() 
{
    cin>>n>>m;
    sum[0]=0;
    for(int i=1;i<=n;i++)
    {
        int a;
        scanf("%d",&a);
        sum[i]=sum[i-1]+a;
    }
    int ans=-inf;
    int h=0,t=0;
    q[1]=0;
    for(int i=1;i<=n;i++)
    {
        while(h<t&&i-q[h+1]>m)h++;
        ans=max(ans,sum[i]-sum[q[h+1]]);
        while(h<t&&sum[i]<=sum[q[t]])t--;
        q[++t]=i;
    }
    printf("%d",ans);
    return 0;
}

2.滑动窗口

题目描述
给定一个大小为n≤106
有一个大小为k的滑动窗口，它从数组的最左边移动到最右边。
您只能在窗口中看到k个数字。
每次滑动窗口向右移动一个位置。
以下是一个例子：
该数组为[1 3 -1 -3 5 3 6 7]，k为3。
窗口位置 最小值 最大值
[1 3 -1] -3 5 3 6 7 -1 3
1 [3 -1 -3] 5 3 6 7 -3 3
1 3 [-1 -3 5] 3 6 7 -3 5
1 3 -1 [-3 5 3] 6 7 -3 5
1 3 -1 -3 [5 3 6] 7 3 6
1 3 -1 -3 5 [3 6 7] 3 7
您的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。
输入
输入包含两行。
第一行包含两个整数 n 和 k，分别代表数组长度和滑动窗口的长度。
第二行有 n个整数，代表数组的具体数值。
同行数据之间用空格隔开。
输出
输出包含两个。
第一行输出，从左至右，每个位置滑动窗口中的最小值。
第二行输出，从左至右，每个位置滑动窗口中的最大值。
样例输入
8 3
1 3 -1 -3 5 3 6 7
样例输出
-1 -3 -3 -3 3 3
3 3 5 5 6 7
题解：
用暴力作法，需要O(nk)的时间复杂度，为了优化降低时间复杂度，可以用单调队列遍历整个数组，找最小值时将前面比新加入的数大的数都删去，每次只取队头，可以将时间复杂度降低到O(n).
3、步骤：
①用一个数组来存储输入的数，用另一个数组存储每个元素在原数组中的下标。
②分为找最大值和找最小值两步来写。
注意事项：
①q数组存储的是原数组中的下标
②注意过程中一些变量的初始值为零，有的地方要加1
③注意什么时候用队头，什么时候用队尾
C o d e : Code: Code:

#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
int n,k;
int a[N],q[N];
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    int h=0,t=-1;
    for(int i=0;i<n;i++)
    {
        while(h<=t&&i-k+1>q[h])h++;
        while(h<=t&&a[q[t]]>=a[i])t--;
        q[++t]=i;
        if(i>=k-1)printf("%d ",a[q[h]]);
    }
    puts("");
    h=0,t=-1;
    for(int i=0;i<n;i++)
    {
        while(h<=t&&i-k+1>q[h])h++;
        while(h<=t&&a[q[t]]<=a[i])t--;
        q[++t]=i;
        if(i>=k-1)printf("%d ",a[q[h]]);
    }
    puts("");
}

3.烽火传递

题目描述
原题来自：NOIP 2010 提高组初赛 · 完善程序
烽火台是重要的军事防御设施，一般建在交通要道或险要处。一旦有军情发生，则白天用浓烟，晚上有火光传递军情。
在某两个城市之间有 nn 座烽火台，每个烽火台发出信号都有一定的代价。为了使情报准确传递，在连续 mm 个烽火台中至少要有一个发出信号。现在输入 n,mn,m 和每个烽火台的代价，请计算总共最少的代价在两城市之间来准确传递情报。
输入
第一行是 n,mn,m，表示 n 个烽火台和连续烽火台数 m；
第二行 nn 个整数表示每个烽火台的代价 a_iai
。
输出
输出仅一个整数，表示最小代价。
样例输入
5 3
1 2 5 6 2
样例输出
4
提示
样例说明
在第 2,52,5 号烽火台上发信号。
题解：
单调队列维护dp
下面主要讲dp思想
设 d p [ i ] dp[i] dp[i]表示从i个烽火台开始被点燃的花费最小值
则 d p [ i ] = m i n ( d p [ i ] , d p [ j ] + a [ i ] ) ( i − m < = j < = i ) dp[i]=min(dp[i],dp[j]+a[i])(i-m<=j<=i) dp[i]=min(dp[i],dp[j]+a[i])(i−m<=j<=i)根据条件 ( i − m < = j < = i ) (i - m <= j <= i) (i−m<=j<=i)可知这是一个区间求单调递增队列问题
C o d e : Code: Code:

#include<bits/stdc++.h>
const int N=2e5+5;
using namespace std;
int n,m;
int a[N],f[N],q[N],ans=0x3f3f3f;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    int h=1,t=1;
    for(int i=1;i<=n;i++)
    {
        while(h<=t&&i-m>q[h])h++;//超出范围
        f[i]=f[q[h]]+a[i];//状态转移方程
        while(h<=t&&f[q[t]]>=f[i])t--;
        q[++t]=i;//q数组存的是编号
    }
    for(int i=n-m+1;i<=n;i++)//注意循环从n-m+1开始，而不是1，因为从1开始不满足m个数目，这样是无解的
        ans=min(ans,f[i]);
    printf("%d\n",ans);
    return 0;
}

这篇关于单调队列【总结】的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！