更好的阅读体验

算法解析

什么是单调队列?

单调队列顾名思义,就是具有单调性质和队列性质的数据结构.

单调队列时间复杂度是多少?为什么是这样的?

单调队列可以保证,对于任何一个数而言,只会在队列中出现一次,一旦这个数对于最后答案没有贡献了,就会及时地将它删除.

一般来说,入队和出队操作满足以下两点.
1. 入队操作:对于一个点而言,如果说它加入队列后满足队列的单调性质,那么我们就可以入队.
2. 出队操作:对于一个点而言,如果说新加入的点,比它更加具有潜力,潜力一般指(拓展性更强,生存能力更高,节点入队时间短.)

因此单调队列的复杂度是我们除了常数复杂度$O(1)$,$O(log)$复杂度级别,第三位最喜欢的线性复杂度$O(n)$,因为这种算法往往代码短,思路好想,符合人类思维.
所以单调队列算法发明者相信,码量适中,思路精简,结构典型的单调队列,一定可以给你的程序员之旅一个有力的帮助.

单调队列适用于那些范围

单调队列,其实是单调栈的一个升级plus版本,或者说是具有[l,r]区间性质的单调栈.(注:单调栈一般来说是[0,r]类型的)

换句话来说,对于单调栈可以做出来的题目,基本上单调队列是可以操作出来的,而且请注意一点,单调队列适用范围更加广阔.
一般来说面对具有区间最优性质问题,并且具有两大性质,单调+队列的数据结构单调队列,往往都可以登上程序的数据结构优化的精彩舞台.

还有单调队列也是动态规划算法一个必备的优化手段,在NOIP,Acm,大公司面试题目中频频出现,所以我们有必要学会这种看似高端大气上档次的数据结构,实际上简易易懂的数据结构.

单调队列算法步骤

1. 对于一个数而言,它可以从队尾入队,必须满足题目的特定条件
2. 对于一个队头的数而言,如果说新来的数,不仅是新来的具有潜力,而且又自身价值还比它价值高,那么不用说队头出队.
3. 总而言之,队列的单调条件,性质如何设置,是我们解题的关键.

题目选讲

第一题

题目描述

原题连接
博览馆正在展出由世上最佳的 M 位画家所画的图画,你想到博览馆去看这些才华横溢的大师们的作品。
可是，那里的博览馆有一个很奇怪的规定，就是在购买门票时必须说明两个数字，
l和r，代表他要看展览中的第 l 幅至第 r 幅画(包含 l 和 r)之间的所有图画，而门票的价钱就是一张图画一元。
为了看到更多名师的画，你希望入场后可以看到所有名师的图画(至少各一张)。
但是你想要花费最少,现在你需要编写计算机程序,来求出最小花费的的 l 值和 r 值。

输入输出格式

输入格式：

第一行是 N 和 M，分别代表博览馆内的图画总数及这些图画是由多少位名师的画所绘画的。
其后的一行包含 N 个数字，它们都介于 1 和 M 之间，代表该位名师的编号。

输出格式：

l和r(l<=r),中间有一个空格,并且题目保证有解,如果多解,输出l最小的.

输入输出样例

输入样例#1：

12 5
2 5 3 1 3 2 4 1 1 5 4 3

输出样例#1：

2 7

数据范围

30%的数据 $N<=200$,$M<=20$
60%的数据 $N<=10^4$,$M<=1000$
100%的数据 $N<=10^6$,$M<=2000$

题意分析

就是你要求出一个区间[l,r],使得这个区间中有M张不同画师的名画,要求满足条件下,区间长度要最短.

思路解析

程序=算法+数据结构.这道题目我们可以利用尺取法(也就是双指针法),当然我们也可以使用数据结构单调队列.
看到这道题目,我们显然要分析这道题目为什么可以用单调队列.

首先我们发现,对于一幅名画而言,如果我当前的候选门票区间,在候选区间的最左端,已经有了和它属于同一个画家的名画的话,那么我们显然是可以抛去之前的老画了,从原来的$[l,r]–>[l+1,r+1]$

因为我现在还没有找到满足所有名家的画都看过的条件,那么我们显然是还要往后找的,但是我要求票价最小,所以说我们必须将$[l,r]–>[l+1,r+1]$.
因为$[l,r]–>[l+1,r+1]$,不同名家画数量一样多,而且$[l+1,r+1]$比$[l,r]$更加具有潜力,拓展性

综上所述,我们这道题目一个隐藏的单调性质就出现了,在加上区间问题,必然具有队列性质,因此我们可以确定数据结构,单调队列无疑了.
切记:我们这里的单调条件就是:名画种类递增!

结构梳理

1. 如果说队头名画,在队列中还有另外一副和它同属一个画家,那么显然队头必须抛弃.
2. 对于每一幅名画,它都可以入队.
3. 对于每一个候选区间,如果它所有类型的名画都集齐了,那么我们就要统计区间费用.

代码实现

dequeSTL版本

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define mk(a,b) make_pair(a,b)
const int N=1e6+5;
int l,r,n,m,a[N],b[N],cnt,ansa=1e9,ansb,ans=1e8;
deque<int> q;
//b数组统计名画种类,q双端队列为单调队列.
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        cin>>a[i];
    for(int i=1; i<=n; i++)
    {
        if (!b[a[i]])//曾经没有出现过
            cnt++;
        //这里特殊注意:因为如果说我们当前区间已经满足题意条件,那么我们后面所有的区间统统都会满足条件,因为我们的出队操作,保证我们必须是名画种类递增.
        q.push_back(i);//名画入选
        b[a[i]]++;
        while(b[a[q.front()]]>=2)//队头名画所代表的画家的画在队列中至少有两幅.
        {
            b[a[q.front()]]--;//队头不要了
            q.pop_front();
        }
        if (cnt>=m && q.back()-q.front()+1<ans)//如果集齐各大名画,同时候选答案区间花费的费用更小.
        {
            ansa=q.front();//l
            ansb=q.back();//r
            ans=q.back()-q.front()+1;//费用
        }
    }
    cout<<ansa<<" "<<ansb<<endl;
    return 0;
}

普通单调队列模拟.

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define mk(a,b) make_pair(a,b)
const int N=1e6+5;
int head,tail;
int l,r,n,m,a[N],b[N],cnt,ansa=1e9,ansb,ans=1e8;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        cin>>a[i];
    head=1,tail=0;
    for(int i=1; i<=n; i++)
    {
        if (!b[a[i]])//未曾出现过
            cnt++;
        tail++;
        b[a[i]]++;
        while(b[a[head]]>=2)
        {
            b[a[head]]--;
            head++;
        }
        if (cnt>=m && tail-head+1<ans)
        {
            ansa=head;
            ansb=tail;
            ans=tail-head+1;
        }
    }
    cout<<ansa<<" "<<ansb<<endl;
    return 0;
}

第二题

题目描述

原题连接
今天是小Z的生日，同学们为他带来了一块蛋糕。这块蛋糕是一个长方体，被用不同色彩分成了$N$个相同的小块，每小块都有对应的幸运值。

小Z作为寿星，自然希望吃到的第一块蛋糕的幸运值总和最大，但小Z最多又只能吃M小块$(M≤N)$的蛋糕。

吃东西自然就不想思考了，于是小Z把这个任务扔给了学OI的你，请你帮他从这N小块中找出连续的k块蛋糕$(k \le M)$，使得其上的幸运值最大。

输入输出格式

输入格式：

输入文件的第一行是两个整数$N,M$。分别代表共有$N$小块蛋糕，小Z最多只能吃$M$小块。
第二行用空格隔开的$N$个整数，第i个整数$P_i$代表第$i$小块蛋糕的幸运值。

输出格式：

输出文件只有一行，一个整数，为小Z能够得到的最大幸运值。

输入输出样例

输入样例#1：

5 2
1 2 3 4 5

输出样例#1：

9

输入样例#2：

6 3
1 -2 3 -4 5 -6

输出样例#2：

5

数据范围

对20%的数据，$N \le 100$。
对100%的数据，$N \le 5*10^{5}$，$|P_i| \le 500$。 答案保证在$2^{31}-1$之内。

题意分析

一句话题意:就是在长度为N的区间里面,找一个长度为K的区间,要求区间的权值最大!

算法解析

首先暴力的思想,我们可以三重循环,两重枚举$[l,r]$,一层统计这个区间的和,然后找到区间值最大的区间.
但是我们发现,其实这道题目可以通过前缀和来优化,然后就变成了两重循环.
综上所述,这道题目差不多算法处理完毕了,但是我们依旧发现,虽然我们优化了一重复杂度,但是数据范围太大,使得我们不得不再次思考如何优化.

对于这道题目而言,我们依旧需要按照程序=算法+数据结构的思维考虑,不过这一次我们可以直接发现这道题目需要使用单调队列.
因为我们发现这道题目,具有以下两点性质.
1. 区间最值问题,而且具有滚动的条件,单调队列的特性.
2. 队列性质,这道题目可以看作一个区间队列.

既然这道题目是区间最值,那么我们可以想到要用单调队列,当时有几个问题如下所示.
1. 我们如何利用单调队列优化?
2. 如何找出这道题目的单调性质是上升还是递减?
3. 单调队列入队出队怎么判断?

首先面对第一个问题,对于单调队列优化,我们可以将区间的值,设置为单调队列每一个元素,既然这样的话,那么第二问题,我们也可以迎刃而解,当然是单调递增的序列.
接着面对第三个问题,入队出队判断.
1. 入队:对于入队操作而言,当然也是所有元素都可以入队.
2. 出队:对于出队操作而言,有一点小小的变化.

首先我们发现,只要当前队列中,队头元素的已经老了,或者说当前队列超过了m个元素,那么我们必须将队头出队.
如果我们发现队列中队尾开始无法满足单调递增了,那么显然破坏了单调性质,我们必须将他们出队.

@[Hikki]

代码实现(有所改动)

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+100;
int a[N],head,tail,n,m,i,j,k,ans,s[N];
deque<int> q;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
        s[i]=s[i-1]+a[i];
    }
    q.push_back(0);//感谢楼下的大佬们.
    for(int i=1; i<=n; i++)
    {
        while(q.size() && q.front()<i-m)//元素个数超过了m限制
            q.pop_front();
        while (q.size() && s[i]<=s[q.back()])//不满足单调递增
            q.pop_back();
        q.push_back(i);//放入队列之中
        if (q.size())//如果队列中有元素
            ans=max(ans,s[i]-s[q.front()]);
    }
    cout<<ans;
    return 0;
}